[Top Interview 150] 226. Invert Binary Tree
Solution)
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
Problem: LeetCode
Reference: NeetCode
Time Complexity: O(2^n)
Space Complexity: O(1)
Explanation)
This recursive function will invert a current node's children.
Base case would be when the root doesn't exist. If it doesn't exist we would simply return Null.
Assuming that the function inverts the current node's children, we'll call the functions that receive the root node's children. This will invert the nodes below the root node's children.
Lastly, we'll invert the root node's children.
Base Case)
As usual, recursion needs to be finished when the root is Null.
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return
Recursive Call)
Since this recursive function will invert the current node's children, we'll make two recursive calls that receives the root's children nodes.
These calls will invert the left and right subtrees of the root node's children.
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return
self.invertTree(root.left)
self.invertTree(root.right)
Final Inversion)
If we have inverted the subtrees of the root node's children, now we gotta invert root node's children.
We can do this by simply swapping them.
After they're swapped, let's return the root node.
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
I tried this problem yesterday, but gave up after spending about two hours. Then I looked at NeetCode's solution video and was in dispair of my foolishness. Maybe I need to ACTUALLY study recursion a bit more. My brain don't function anymore.