101. Symmetric Tree

Difficulty:
Related Topics:
Similar Questions:

    Problem

    Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

    For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
       / \
      2   2
     / \ / \
    3  4 4  3
    

    But the following [1,2,2,null,3,null,3] is not:

    1
       / \
      2   2
       \   \
       3    3
    

    Note: Bonus points if you could solve it both recursively and iteratively.

    Solution 1

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {boolean}
     */
    var isSymmetric = function(root) {
      if (!root) return true;
      return helper(root.left, root.right);
    };
    
    var helper = function (p, q) {
      if ((!p && q) || (p && !q) || (p && q && p.val !== q.val)) return false;
      if (p && q) return helper(p.left, q.right) && helper(p.right, q.left);
      return true;
    };
    

    Explain:

    nope.

    Complexity:

    Solution 2

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {boolean}
     */
    var isSymmetric = function(root) {
      if (!root) return true;
    
      var p = [root.left];
      var q = [root.right];
      var ll = null;
      var rr = null;
    
      while (p.length && q.length) {
        ll = p.pop();
        rr = q.pop();
    
        if (!ll && !rr) continue;
        if (!ll || !rr) return false;
        if (ll.val !== rr.val) return false;
    
        p.push(ll.left);
        p.push(ll.right);
        q.push(rr.right);
        q.push(rr.left);
      }
    
      return true;
    };
    

    Explain:

    nope.

    Complexity: