100. Same Tree

Difficulty:
Related Topics:
Similar Questions:

    Problem

    Given two binary trees, write a function to check if they are the same or not.

    Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

    Example 1:

    Input:     1         1
              / \       / \
             2   3     2   3
    
            [1,2,3],   [1,2,3]
    
    Output: true
    

    Example 2:

    Input:     1         1
              /           \
             2             2
    
            [1,2],     [1,null,2]
    
    Output: false
    

    Example 3:

    Input:     1         1
              / \       / \
             2   1     1   2
    
            [1,2,1],   [1,1,2]
    
    Output: false
    

    Solution 1

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} p
     * @param {TreeNode} q
     * @return {boolean}
     */
    var isSameTree = function(p, q) {
      if ((!p && q) || (p && !q) || (p && q && p.val !== q.val)) return false;
      if (p && q) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
      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} p
     * @param {TreeNode} q
     * @return {boolean}
     */
    var isSameTree = function(p, q) {
      var s1 = [p];
      var s2 = [q];
      var ll = null;
      var rr = null;
    
      while (s1.length && s2.length) {
        ll = s1.pop();
        rr = s2.pop();
    
        if (!ll && !rr) continue;
        if (!ll || !rr) return false;
        if (ll.val !== rr.val) return false;
    
        s1.push(ll.left);
        s1.push(ll.right);
        s2.push(rr.left);
        s2.push(rr.right);
      }
    
      return true;
    };
    

    Explain:

    nope.

    Complexity: