Invert Binary Tree
Problem Statement
You are given the root of a binary tree root
. Invert the binary tree and return its root.
Example 1:
# Input: root = [1,2,3,4,5,6,7]# Output: [1,3,2,7,6,5,4]
Example 2:
# Input: root = [3,2,1]# Output: [3,1,2]
Example 3:
# Input: root = []# Output: []
Constraints:
0 <= The number of nodes in the tree <= 100
.-100 <= Node.val <= 100
You should aim for a solution with O(n)
time and O(n)
space, where n
is the number of nodes in the tree.
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(n)
space, where n
is the number of nodes in the tree.
Hint 1
From the diagram, you can see that the left and right children of every node in the tree are swapped. Can you think of a way to achieve this recursively? Maybe an algorithm that is helpful to traverse the tree.
Hint 2
We can use the Depth First Search (DFS) algorithm. At each node, we swap its left and right children by swapping their pointers. This inverts the current node, but every node in the tree also needs to be inverted. To achieve this, we recursively visit the left and right children and perform the same operation. If the current node is null
, we simply return.
Solution
Breadth First Search
from collections import dequefrom typing import Optional
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
def invert_tree_bfs(root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None queue = deque([root]) while queue: node = queue.popleft() node.left, node.right = node.right, node.left if node.left: queue.append(node.left) if node.right: queue.append(node.right) return root
Time complexity: O(n)
Space complexity: O(n)
Depth First Search
from typing import Optional
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
def invert_tree_dfs(root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None
root.left, root.right = root.right, root.left
invert_tree_dfs(root.left) invert_tree_dfs(root.right)
return root
Time complexity: O(n)
Space complexity: O(n)
Iterative DFS
from typing import Optional
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
def invert_tree_iterative_dfs(root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None stack = [root] while stack: node = stack.pop() node.left, node.right = node.right, node.left if node.left: stack.append(node.left) if node.right: stack.append(node.right) return root
Time complexity: O(n)
Space complexity: O(n)