Description
Given the root of a binary tree, invert the tree, and return its root.
Examples:
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]
Example 3:
Input: root = []
Output: []Solution in Python
Approach:
- Base Case:
- If the
rootisNone(empty tree), we simply returnNone.
- If the
- Recursive Inversion:
- For each node, we recursively invert its left and right subtrees.
- Once the subtrees are inverted, we swap the left and right children of the current node.
- Return the Inverted Tree:
- After swapping the left and right subtrees, return the
root, which now represents the root of the inverted tree.
- After swapping the left and right subtrees, return the
Steps:
- Check if the root is
None. If so, returnNone. - Recursively invert the left subtree.
- Recursively invert the right subtree.
- Swap the left and right subtrees of the current node.
- Return the current node, which now represents the root of the inverted subtree.
Python
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# Base case: if the root is None, return None
if root is None:
return None
# Recursive case: invert the left and right subtrees
left_inverted = self.invertTree(root.left) # Invert the left subtree
right_inverted = self.invertTree(root.right) # Invert the right subtree
# Swap the left and right subtrees
root.left = right_inverted
root.right = left_inverted
# Return the root, which now represents the inverted tree
return rootExplanation:
- Base Case:
- If the
rootisNone, the function immediately returnsNone. This handles the case where the tree is empty or we have reached a leaf node’s child.
- If the
- Recursive Case:
- We first invert the left subtree and store the result in
left_inverted. - Similarly, we invert the right subtree and store the result in
right_inverted.
- We first invert the left subtree and store the result in
- Swapping:
- Once we have the inverted left and right subtrees, we swap them by assigning
root.lefttoright_invertedandroot.righttoleft_inverted.
- Once we have the inverted left and right subtrees, we swap them by assigning
- Return:
- Finally, the
root(with its children swapped) is returned.
- Finally, the
Time Complexity:
- O(n): where
nis the number of nodes in the tree. Each node is visited exactly once, and the inversion operation at each node takes constant time.
Space Complexity:
- O(h): where
his the height of the tree. This accounts for the recursion stack. In the worst case, the height of the tree could ben(in a skewed tree), making the space complexity O(n). In the best case (balanced tree), the height is O(log n).
Solution in Javascript
JavaScript
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
// Base case: if the root is null, return null (empty tree or leaf node's child)
if (root === null) {
return null;
}
// Recursively invert the left and right subtrees
let leftInverted = invertTree(root.left); // Invert the left subtree
let rightInverted = invertTree(root.right); // Invert the right subtree
// Swap the left and right children of the current node
root.left = rightInverted;
root.right = leftInverted;
// Return the root, which now represents the inverted tree
return root;
};
Solution in Java
Java
class Solution {
public TreeNode invertTree(TreeNode root) {
// Base case: if the root is null, return null (empty tree or leaf node's child)
if (root == null) {
return null;
}
// Recursively invert the left and right subtrees
TreeNode leftInverted = invertTree(root.left); // Invert the left subtree
TreeNode rightInverted = invertTree(root.right); // Invert the right subtree
// Swap the left and right children of the current node
root.left = rightInverted;
root.right = leftInverted;
// Return the root, which now represents the inverted tree
return root;
}
}Solution in C#
C#
public class Solution {
public TreeNode InvertTree(TreeNode root) {
// Base case: If the root is null, return null (empty tree or leaf node's child)
if (root == null) {
return null;
}
// Recursively invert the left and right subtrees
TreeNode leftInverted = InvertTree(root.left); // Invert the left subtree
TreeNode rightInverted = InvertTree(root.right); // Invert the right subtree
// Swap the left and right children of the current node
root.left = rightInverted;
root.right = leftInverted;
// Return the root, which now represents the inverted tree
return root;
}
}