一天一大 lee(相同的树)难度:简单-Day20200807

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
  // 判断到最终节点相同 返回true
  if (p === null && q === null) return true
  // 两个树不是同时遇到最终节点 返回false
  if (p === null || q === null) return false
  // 传入节点是否相同
  if (p.val !== q.val) return false
  // 递归判断每个节点的左右节点
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

var isSameTree = function (p, q) {
  // 判断到最终节点相同 返回true
  if (p === null && q === null) return true
  // 两个树不是同时遇到最终节点 返回false
  if (p === null || q === null) return false

  let dp1 = [p],
    dp2 = [q]

  while (dp1.length && dp2.length) {
    let node1 = dp1.shift(),
      node2 = dp2.shift()
    if (node1.val != node2.val) {
      return false
    }
    let left1 = node1.left,
      right1 = node1.right,
      left2 = node2.left,
      right2 = node2.right
    // 异或，均为false或者均为true 结果为false，不然为true
    if ((left1 === null) ^ (left2 === null)) return false
    if ((right1 === null) ^ (right2 === null)) return false
    // 该节点相同，继续推送下一个节点进行比较
    if (left1 !== null) dp1.push(left1)
    if (right1 !== null) dp1.push(right1)
    if (left2 !== null) dp2.push(left2)
    if (right2 !== null) dp2.push(right2)
  }
  // 所有节点比较完成返回true
  return dp1.length === 0 && dp2.length === 0
}