226. Invert Binary Tree ๐
Difficulty: Easy
- Tags: Binary Tree
, DFS
, BFS
, Recursion
Problem Statement ๐
Given the root of a binary tree, invert the tree (swap the left and right subtrees), and return its root.
Examples ๐
๐น Example 1:
Input:
Output:
๐น Example 2:
Input:
Output:
๐น Example 3:
Input:
Output:
Constraints โ๏ธ
The number of nodes in the tree is in the range
[0, 100]
.-100 <= Node.val <= 100
.
Solution ๐ก
To invert a binary tree:
Swap the left and right children of the current node.
Recursively apply the same operation for each child.
Java Solution (Recursive Approach)
Explanation of the Solution
Base Case: If the current node is
null
, returnnull
.Swap the left and right children of the node.
Recursively call
invertTree
for the left and right subtrees.Return the root after performing all swaps.
Java Solution (Iterative Approach with Queue)
Time Complexity โณ
O(n), where
n
is the number of nodes in the tree. Each node is visited once.
Space Complexity ๐พ
O(h) for the recursive approach, where
h
is the height of the tree (stack space for recursion).O(n) for the iterative approach due to the queue.
Follow-up ๐ง
How would you modify the solution for a n-ary tree?
Implement a solution to invert a binary tree in postorder traversal.
Last updated