🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires swapping the left and right children of all nodes in the binary tree. This can be efficiently achieved using a recursive approach where we swap the children of each node and then recursively apply the same operation to the left and right subtrees.
Approach
- Base Case:
- If the current node (
root
) isNone
, return immediately as there's nothing to invert. - Swap Children: - Swap the left and right children of the current node.
- Recursive Inversion: - Recursively call the inversion function on the left child of the current node. - Recursively call the inversion function on the right child of the current node.
- Return Root: - Return the root of the tree after inverting all its nodes.
The recursive approach ensures that every node's children are swapped, effectively inverting the entire tree.
Complexity
Time Complexity:
O(N), where N is the number of nodes in the binary tree. Each node is visited once.
Space Complexity:
O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).
Code
C++
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
helper(root);
return root;
}
private:
void helper(TreeNode* root) {
if (root == nullptr) return;
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
helper(root->left);
helper(root->right);
}
};
Python
# 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: Optional[TreeNode]) -> Optional[TreeNode]:
self.helper(root)
return root
def helper(self, root: Optional[TreeNode]):
if root is None:
return
root.left, root.right = root.right, root.left
# Recursively invert the left and right subtrees
self.helper(root.left)
self.helper(root.right)
Java
class Solution {
public TreeNode invertTree(TreeNode root) {
helper(root);
return root;
}
private void helper(TreeNode root) {
if (root == null) return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
helper(root.left);
helper(root.right);
}
}
JavaScript
var invertTree = function(root) {
helper(root);
return root;
};
function helper(root){
if(root == null) return;
let temp = root.left;
root.left = root.right;
root.right = temp;
helper(root.left);
helper(root.right);
}