Description
https://leetcode.com/problems/invert-binary-tree/
Invert a binary tree.
Example:
Input:
4 / \ 2 7 / \ / \ 1 3 6 9
Output:
4 / \ 7 2 / \ / \ 9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
Explanation
Invert left and right subtrees.
Python 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: TreeNode) -> TreeNode:
return self.helper(root)
def helper(self, root):
if not root:
return root
if not root.left and not root.right:
return root
left = self.helper(root.left)
right = self.helper(root.right)
root.left = right
root.right = left
return root- Time Complexity: O(N)
- Space Complexity: O(1)