Problem Statement:
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: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- Base Case: If the current node is
null, returnnull. - Swap the left and right child of the current node.
- Recurse on the left and right subtrees.
- Finally, return the root node (which now has inverted subtrees).
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Initial Queue: [2, 3]
Step 1:
→ p1 = 2, p2 = 3
→ p1 and p2 are not null → OK
→ Compare p1.val (2) != p2.val (3)
→ Values are not equal → Return false
Function exits early.
Final Result: false
Step 1:
→ p1 = 2, p2 = 3
→ p1 and p2 are not null → OK
→ Compare p1.val (2) != p2.val (3)
→ Values are not equal → Return false
Function exits early.
Final Result: false
var isSymmetric = function(root) {
let q = [root.left, root.right];
while(q.length) {
let p1 = q.shift();
let p2 = q.shift();
if(!p1 && !p2) continue;
if(!p1 || !p2) return false;
if(p1.val != p2.val) return false;
q.push(p1.left, p2.right);
q.push(p1.right, p2.left);
}
return true;
};
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root):
if not root:
return root
root.left, root.right = root.right, root.left
invertTree(root.left)
invertTree(root.right)
return root
class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
TreeNode* invertTree(TreeNode* root) {
if (!root) return root;
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
invertTree(root->left);
invertTree(root->right);
return root;
}
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* invertTree(struct TreeNode* root) {
if (!root) return root;
struct TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
invertTree(root->left);
invertTree(root->right);
return root;
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
public class Solution {
public TreeNode InvertTree(TreeNode root) {
if (root == null) return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
InvertTree(root.left);
InvertTree(root.right);
return root;
}
}
