Binary Tree Equal

思路

给定两个二叉树的根节点 a 和 b，需要判断它们是否完全相同。

两个二叉树相同的条件是：

• 结构相同
• 对应位置的节点值相同

也就是说，每一个位置上要么两边同时是 null，要么两边同时是非 null 且 val 相等，同时左右子树也必须完全一致。

算法步骤

使用递归比较：

1. 若 a 和 b 都是 null，则相同，返回 true
2. 若一个 null，一个非 null，则结构不同，返回 false
3. 若 a.val !== b.val，则值不同，返回 false
4. 继续递归比较左子树、右子树 return isSame(a.left, b.left) && isSame(a.right, b.right)

• 时间复杂度：O(n)，n 是节点总数，需要遍历所有节点
• 空间复杂度：O(h)，h 是树的高度，递归深度取决于树结构（最坏 O(n)）

代码

function isSameTree(a: TreeNode | null, b: TreeNode | null): boolean {
  if (a === null && b === null) return true;
  if (a === null || b === null) return false;
  if (a.val !== b.val) return false;

  return isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
}