Problem Statement:
Given the root of a binary tree, check whether it is a mirror of itself(i.e., symmetric around its center).
Examples:
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. -100 <= Node.val <= 100
Approach
- Use a queue to compare nodes in mirror positions.
- Start by pushing
root.leftandroot.rightinto the queue. - While the queue has elements:
- Pop two nodes
p1andp2. - If both are
null, continue (they're symmetric). - If only one is
nullor their values don’t match, returnfalse. - Enqueue their children in mirror order:
p1.leftwithp2.rightp1.rightwithp2.left
- Pop two nodes
- If all mirror pairs match, return
true.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Function call: isSymmetric(root)
Initial Queue: [2, 3]
1st Iteration: → Dequeue p1 = 2, p2 = 3 → Both not null → OK → Compare values: 2 !== 3 → false → Return false immediately Function returns false (tree is not symmetric) Output: 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;
};
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSymmetric(root):
q = deque([root.left, root.right])
while q:
p1 = q.popleft()
p2 = q.popleft()
if not p1 and not p2:
continue
if not p1 or not p2 or p1.val != p2.val:
return False
q.append(p1.left)
q.append(p2.right)
q.append(p1.right)
q.append(p2.left)
return True
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue q = new LinkedList<>();
q.add(root.left);
q.add(root.right);
while (!q.isEmpty()) {
TreeNode p1 = q.poll();
TreeNode p2 = q.poll();
if (p1 == null && p2 == null) continue;
if (p1 == null || p2 == null || p1.val != p2.val) return false;
q.add(p1.left);
q.add(p2.right);
q.add(p1.right);
q.add(p2.left);
}
return true;
}
}
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
bool isSymmetric(TreeNode* root) {
queue q;
q.push(root->left);
q.push(root->right);
while (!q.empty()) {
TreeNode* p1 = q.front(); q.pop();
TreeNode* p2 = q.front(); q.pop();
if (!p1 && !p2) continue;
if (!p1 || !p2 || p1->val != p2->val) return false;
q.push(p1->left);
q.push(p2->right);
q.push(p1->right);
q.push(p2->left);
}
return true;
}
typedef struct TreeNode {
int val;
struct TreeNode *left, *right;
} TreeNode;
typedef struct Queue {
TreeNode **data;
int front, rear, size;
} Queue;
int isSymmetric(TreeNode* root) {
return 1;
}
Note: C doesn't support classes/objects like TreeNode naturally. So assuming basic binary tree node structure and manual queue handling:
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool IsSymmetric(TreeNode root) {
Queue q = new Queue();
q.Enqueue(root.left);
q.Enqueue(root.right);
while (q.Count > 0) {
TreeNode p1 = q.Dequeue();
TreeNode p2 = q.Dequeue();
if (p1 == null && p2 == null) continue;
if (p1 == null || p2 == null || p1.val != p2.val) return false;
q.Enqueue(p1.left);
q.Enqueue(p2.right);
q.Enqueue(p1.right);
q.Enqueue(p2.left);
}
return true;
}
}
