100. 相同的树

[Geekhyt]

原题链接

深度优先搜索 DFS

1.如果两个二叉树都为空，则它们相同返回 true。
2.如果两个二叉树中有一个为空，则它们不同返回 false。
3.如果两个二叉树都不为空，首先判断根节点是否相同，不同则返回 false。
4.如果两个二叉树的根节点相同，则分别递归判断其左右子树是否相同。

const isSameTree = function(p, q) {
    if (p === null && q === null) return true;
    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);
};

• 时间复杂度: O(min(m, n))
• 空间复杂度: O(min(m, n))

[lywq9296]

// BFS迭代法

1. 初始化队列，并存入两颗树的根节点
2. 遍历两棵树的节点，依次入队root1.left, root2.left, root1.right, root2.right
3. 对出队节点校验：
4. 如果一个有一个为空，返回 false
5. 如果两个节点的 val 不同，返回 false
6. 如果两个节点都为 null，跳过

var isSameTree = function(p, q) {
  if(!p && !q){
    return true
  }
  let queue = [p, q];
  while（queue.length){
    let root1 = queue.shift();
    let root2 = queue.shift();

    if(!root1 && !root2) {
      continue;
    }

    if(root1 && root2 && root1.val  !==  root2.val){
      return false
    }
    
    if(!root1 || !root2){
      return false
    }
	
    queue.push(root1.left, root2.left);
    queue.push(root1.right, root2.right);
  }
  return true;
}