力扣链接：100.相同的树

难度：⭐

✏️ 方法一：

解题关键词：二叉树、递归

解题思路：递归判断节点是否相同，如果一个为 null，另一个不为 null，那么就不相同，如果两个都是 null， 那么就相同，如果都不为 null，且都不为空，那么判断它们的值，之后继续递归它们的左右子树。

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  // 如果都为 null，就是相同的
  if (p === null && q === null) return true;

  // 如果其中一个为 null，那么不相同
  if (p === null && q !== null) return false;
  if (p !== null && q === null) return false;

  // 如果两个 value 不同，那么就不是相同的树
  if (p.val !== q.val) return false;

  // 递归对比左右子树
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

✏️ 方法二：

解题关键词：二叉树、层序遍历

解题思路：用两个队列分别存储，然后挨个节点取出来判断是否相同。

:::error 请注意对称的情况，要把空位置变成 null 然后 push 进去 :::

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  // 都为 null
  if (p === null && q === null) return true;
  // 有一个为 null，一个不为 null
  if (p === null || q === null) return false;
  // 两个的值不一样
  if (p.val !== q.val) return false;

  // 队列1
  const queue1: TreeNode[] = [p];
  // 队列2
  const queue2: TreeNode[] = [q];

  while (queue1.length && queue2.length) {
    const node1 = queue1.shift();
    const node2 = queue2.shift();

    // 如果两个 node 都为 null，继续比较剩下的
    if (node1 === null && node2 === null) continue;
    // 如果有一个为 null，有一个不为 null
    if (node1 === null || node2 === null) return false;
    // 值不一样
    if (node1.val !== node2.val) return false;

    // 将左右节点都 push 进去
    queue1.push(node1.left, node1.right);
    queue2.push(node2.left, node2.right);
  }

  return !queue1.length && !queue2.length;
}