-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathInvertBinaryTree.py
191 lines (156 loc) · 6.8 KB
/
InvertBinaryTree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#Given the root of a binary tree, invert the tree, and return its root.
#Example 1:
#Input: root = [4,2,7,1,3,6,9]
#Output: [4,7,2,9,6,3,1]
#Example 2:
#Input: root = [2,1,3]
#Output: [2,3,1]
#Example 3:
#Input: root = []
#Output: []
#Constraints:
#The number of nodes in the tree is in the range [0, 100].
#-100 <= Node.val <= 100
#Solution:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
#here, root represents the entire binary tree as shown by the method signature, and we want to check that a tree exists before proceeding - root:Optional[TreeNode]
if not root: #base case as terminating condition when we've reached bottom of tree. Returns None if there is not another node below the current node and applies to both the left and right tree.
return None
#Swap the left and right children of the current Node
#root.right overtakes root.left, and root.left overtakes root.right
root.left, root.right = root.right, root.left
#Recursively invert the left and right subtrees
#This line is just recalling the entire invertTree function except moving down one node to the left
self.invertTree(root.left) # just means passing the new left node as an argument and executing all code in the function again
self.invertTree(root.right)
return root #return root meaning return the entire tree after it's inverted because it would make sense as root is the tree itself. you can tell that root is tree because root is 4 2 7 1 3 6 9, and the picture shows that the tree consists of 4 2 7 1 3 6 9, so it makes sense that root is equal to tree or the tree itself.
#note that, in a binary tree, the left side is smaller than the right side
#invert binary tree basically is flipping the children and then going to the left child, and flipping (literally just swapping places) that left child's children, and then going to the right child, flipping that right child's children, and keep going until you reach the bottom of the tree.
#if the three is
#. a
# b c
#. d e f
# we are flipping the 2nd level, and then we are flipping the 2nd level's children, and we keep doing this until we reach the bottom
# a
# c b
#. d e f
# when a level has an odd number of nodes, the middle one stays, but the left and right are swapped, but when the level has an even number of nodes, the left becomes the right, and the right becomes the left
# inverting means like anagram backwards, not just replacing the left side with the right side, so 1 3 6 9 should become 9 6 3 1 (backwards to forwards), not 6 9 1 3.
#6/9/23 refresher (my solution):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
#12/25/23 refresher ( my solution with my own explanation):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
#if root is None, then none == none, so there's nothing to invert, so just return the root becuase it's already inverted
#this is also base case if we hit bottom of subtree itself since, at the bottom, there's nothing to invert, so just return root for that particular function call that started it - either l or r
if root is None:
return root
#swap left and right nodes at current level of tree
root.left, root.right = root.right, root.left
#recurvisely go down until hitting bottom of left
l = self.invertTree(root.left)
r = self.invertTree(root.right)
return root
#3/5/24:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root == None:
return
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
#my own solution python3 4/29/24:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def f(root):
if root == None:
return None
root.left, root.right = root.right, root.left
l = f(root.left)
r = f(root.right)
return root
return f(root)
#5/27/24 review:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
root.left, root.right = root.right, root.left
l = self.invertTree(root.left)
r = self.invertTree(root.right)
return root
#7/31/24 refresher:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
l = self.invertTree(root.left)
r = self.invertTree(root.right)
return root
#10/26/24 review:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root