forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbhyun-kim.py
More file actions
42 lines (32 loc) · 1.13 KB
/
bhyun-kim.py
File metadata and controls
42 lines (32 loc) · 1.13 KB
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
"""
226. Invert Binary Tree
https://leetcode.com/problems/invert-binary-tree/description/
Solution
Recursively swaps the left and right children of the root node.
1. Check if the root has left and right children.
2. If it does, invert the left and right children.
3. If it doesn't, invert the left or right child.
4. Return the root.
Time complexity: O(n)
Space complexity: O(n)
"""
from typing import Optional
# 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]:
has_left = hasattr(root, "left")
has_right = hasattr(root, "right")
if has_left and has_right:
root.left, root.right = self.invertTree(root.right), self.invertTree(
root.left
)
elif has_left:
root.left, root.right = None, self.invertTree(root.left)
elif has_right:
root.left, root.right = self.invertTree(root.right), None
return root