Invert Binary Tree
Invert a binary tree. Given the root of a binary tree, invert the tree, and return its root.
Constraints:
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Examples:
Input: [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Explanation: The inverted binary tree is: 4 / \ 7 2 / \ / \ 9 6 3 1
Solutions
Recursive Approach
Time: O(n)Space: O(h)
This solution uses a recursive approach to invert the binary tree. It first checks if the root is null, and if so, returns null. Then, it swaps the left and right child nodes of the root. Finally, it recursively calls the invertTree function on the left and right child nodes.
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}Follow-up:
How would you invert a binary tree iteratively?
