forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathinvert-binary-tree.py
More file actions
executable file
·36 lines (31 loc) · 841 Bytes
/
Copy pathinvert-binary-tree.py
File metadata and controls
executable file
·36 lines (31 loc) · 841 Bytes
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
"""
Recursive
Time: O(N)
Space: O(LogN)
"""
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return root
left = root.left
right = root.right
root.left = self.invertTree(right)
root.right = self.invertTree(left)
return root
"""
Iterative
Time: O(N)
Space: O(N)
"""
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return root
q = collections.deque([root])
while q:
node = q.popleft()
left = node.left
right = node.right
node.right = left
node.left = right
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return root