## 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;
}
``````
Copy The Code &

Input

cmd
root = [1,2,2,3,4,4,3]

Output

cmd
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;
}
};
``````
Copy The Code &

Input

cmd
root = [1,2,2,3,4,4,3]

Output

cmd
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);
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,2,null,3,null,3]

Output

cmd
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
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,2,null,3,null,3]

Output

cmd
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
``````
Copy The Code &

Input

cmd
root = [1,2,2,3,4,4,3]

Output

cmd
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);
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,2,3,4,4,3]

Output

cmd
true
Advertisements