Algorithm
Problem Nmae: 101. Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define PUSH(N) do { p[n ++] = N; } while (0)
bool isSymmetric(struct TreeNode* root) {
struct TreeNode **p, **tmp;
int dep, n, i, j, k;
if (!root) return true;
dep = 0; n = 0;
p = malloc((1 << dep) * sizeof(struct TreeNode *));
//assert(p);
PUSH(root);
while (n) {
for (i = 0, j = n - 1; i < j; i ++, j --) {
if ((!p[i] && p[j]) ||
(!p[j] && p[i]) ||
( p[i] && p[i]->val != p[j]->val)) {
free(p);
return false;
}
}
tmp = p; k = n;
dep ++; n = 0;
p = malloc((1 << dep) * sizeof(struct TreeNode *));
//assert(p);
for (i = 0; i < k; i ++) {
if (tmp[i]) {
PUSH(tmp[i]->left);
PUSH(tmp[i]->right);
}
}
free(tmp);
}
free(p);
return true;
}
Input
root = [1,2,2,3,4,4,3]
Output
true
#2 Code Example with C++ Programming
Code -
C++ Programming
// Recursive
class Solution {
public:
bool isSymmetric(TreeNode* root) {
vector<vector<TreeNode*>>v;
dfs(root, v, 0);
return check(v);
}
void dfs(TreeNode* root, vector < vector<TreeNode*>>& v, int level){
if(level == v.size()) v.push_back({});
v[level].push_back(root);
if(!root) return;
dfs(root->left, v, level + 1);
dfs(root->right, v, level + 1);
}
bool check(vector<vector < TreeNode*>>& v){
for(auto x: v){
int l = 0, r = x.size() - 1;
while(l < r){
auto a = x[l++];
auto b = x[r--];
if((!a || !b) && (a || b) || (a && b> && (a->val != b->val)) return false;
}
}
return true;
}
};
// Iterative
class Solution {
public:
bool isSymmetric(TreeNode* root) {
vector < vector<TreeNode*>>v;
queue < TreeNode*>cur, next;
cur.push(root);
int level = 0;
while(!cur.empty()){
auto p = cur.front();
cur.pop();
if(v.size() == level) v.push_back({});
v[level].push_back(p);
if(p){
next.push(p->left);
next.push(p->right);
}
if(cur.empty()){
level++;
swap(cur, next);
}
}
return check(v);
}
bool check(vector<vector < TreeNode*>>& v){
for(auto x: v){
int l = 0, r = x.size() - 1;
while(l < r){
auto a = x[l++];
auto b = x[r--];
if((!a || !b) && (a || b) || (a && b> && (a->val != b->val)) return false;
}
}
return true;
}
};
Input
root = [1,2,2,3,4,4,3]
Output
true
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isSymmetric(TreeNode root) {
return helper(root.left, root.right);
}
private boolean helper(TreeNode leftNode, TreeNode rightNode) {
if (leftNode == null && rightNode == null) {
return true;
}
if ((leftNode == null || rightNode == null) || leftNode.val != rightNode.val) {
return false;
}
return helper(leftNode.left, rightNode.right) && helper(leftNode.right, rightNode.left);
}
}
Input
root = [1,2,2,null,3,null,3]
Output
false
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const isSymmetric = function(root) {
if(root == null) return true
return compare(root.left, root.right)
};
function compare(l, r) {
if(l == null && r == null) return true
if( (l == null && r != null) || (l != null && r == null) ) return false
if(l.val === r.val) {
if(compare(l.left, r.right) !== false && compare(l.right, r.left) !== false) {
return true
} else {
return false
}
} else {
return false
}
}
Input
root = [1,2,2,null,3,null,3]
Output
false
#5 Code Example with Python Programming
Code -
Python Programming
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
else:
return self.isMirror(root.left, root.right)
def isMirror(self, left, right):
if left is None and right is None:
return True
if left is None or right is None:
return False
if left.val == right.val:
outPair = self.isMirror(left.left, right.right)
inPiar = self.isMirror(left.right, right.left)
return outPair and inPiar
else:
return False
Input
root = [1,2,2,3,4,4,3]
Output
true
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _101_SymmetricTree
{
public bool IsSymmetric(TreeNode root)
{
if (root == null) return true;
return isMirror(root.left, root.right);
}
private bool isMirror(TreeNode root1, TreeNode root2)
{
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
if (root1.val != root2.val) return false;
return isMirror(root1.left, root2.right) && isMirror(root1.right, root2.left);
}
}
}
Input
root = [1,2,2,3,4,4,3]
Output
true