46. Invert Binary Tree
Mirror a binary tree: swap the left and right child of every node. Return the root.
Example 1
Input:
root = [4,2,7,1,3,6,9]Output:
[4,7,2,9,6,3,1]Example 2
Input:
root = [2,1,3]Output:
[2,3,1]Hint 1
Swap the children of the root, then invert each subtree.
Approach 1: Recursion ✅
Swap children at every node.
⏱ Time O(n)💾 Space O(h)
Reference solution for Recursion (time O(n), space O(h)). Each solution passes every test in all four languages.
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root:
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return rootclass Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left);
root.left = invertTree(root.right);
root.right = left;
return root;
}
}class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};function invertTree(root) {
if (!root) return null;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
}Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.
Watch the core idea of this problem step by step. Change the input and press Visualize.
Explained in the lesson Binary Trees & BSTs.
Run your code to see results here.