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 & Try With Live Editor

Input

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

Output

x
+
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 & Try With Live Editor

Input

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

Output

x
+
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 & Try With Live Editor

Input

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

Output

x
+
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 & Try With Live Editor

Input

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

Output

x
+
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 & Try With Live Editor

Input

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

Output

x
+
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 & Try With Live Editor

Input

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

Output

x
+
cmd
true
Advertisements

Demonstration


Previous
#100 Leetcode Same Tree Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#102 Leetcode Binary Tree Level Order Traversal Solution in C, C++, Java, JavaScript, Python, C# Leetcode