020 · Same Tree
My First Thoughts
看到这道题，第一反应是：
判断每个节点是否相同，相同就继续递归；某个地方不同，就直接返回
False。
这个方向是对的。
因为两棵树要相同，不只是根节点的值一样，还要求：
- 当前节点的值一样
- 左子树一样
- 右子树一样
也就是说，对于每一对节点 p 和 q，我们都要比较三个部分：
val
left
right一开始可能会写出类似这样的想法：
def same_tree(p, q):
if p.val != q.val or p.left != q.left or p.right != q.right:
return False
same_tree(p.left, q.left)
same_tree(p.right, q.right)
return True这段代码表达了一个重要想法：每次都比较当前节点的状态，然后继续比较左右分支。
但它还不能直接作为最终答案，因为递归里的几个关键边界还没有处理清楚。
Why That Is Not Enough
主要有两个问题。
第一，不能一上来就访问 p.val 和 q.val。
如果 p 或 q 是 None，那么下面这句会直接报错：
p.val所以在比较节点值之前，必须先判断空节点。
空节点有两种情况：
p 和 q 都是 None → 这部分相同
p 和 q 只有一个是 None → 结构不同第二，递归调用的结果要被返回。
如果只是写：
same_tree(p.left, q.left)
same_tree(p.right, q.right)
return True那么即使左子树或右子树已经返回了 False，最后仍然会返回 True。
所以左右子树的结果必须合并起来：
return same_tree(p.left, q.left) and same_tree(p.right, q.right)这句话的意思是：左子树相同，并且右子树也相同，当前这棵树才算相同。
Final Idea
用递归同时比较两棵树。
递归函数可以定义成：
isSameTree(p, q)返回以p和q为根节点的两棵树是否相同。
每次递归都处理一对节点。
先处理空节点：
if p is None and q is None:
return True两个节点都为空，说明这两个位置都没有节点，结构在这里是相同的。
再处理只有一个为空的情况：
if p is None or q is None:
return False一个位置有节点，另一个位置没有节点，结构不同。
接着比较当前节点的值：
if p.val != q.val:
return False当前节点值不同，两棵树也不可能相同。
如果上面三关都通过，就继续比较左右子树：
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)以这两棵树为例：
1 1
/ \ / \
2 3 2 3递归关系可以这样看：
isSameTree(1, 1)
├── isSameTree(2, 2) → True
└── isSameTree(3, 3) → True
=> True and True
=> True如果结构不同：
1 1
/ \
2 2递归到左边时会遇到：
isSameTree(2, None) → False所以整棵树直接判断为不同。
Why It Works
两棵二叉树相同，需要满足一个递归条件：
当前节点相同
左子树相同
右子树相同递归函数 isSameTree(p, q) 的含义很明确：判断以 p 和 q 为根节点的两棵树是否相同。
对于任意一对节点：
- 两个都为空，说明这一部分相同
- 只有一个为空，说明结构不同
- 两个都不为空，但值不同，说明节点内容不同
- 当前节点值相同，就继续比较左子树和右子树
因为每个位置都按同样规则比较，而且左右子树都必须返回 True，所以只有结构和值完全一致时，最终才会返回 True。
Code
def isSameTree(p, q):
if p is None and q is None:
return True
if p is None or q is None:
return False
if p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)Complexity
| Time | \(O(n)\) — 每个位置最多比较一次，n 是两棵树中节点数量较大的那个 |
| Space | \(O(h)\) — 递归调用栈的深度等于树的高度 h，最坏情况下（树退化成一条链）是 \(O(n)\) |
Takeaway
判断两棵树是否相同，不是只看当前节点，也不是直接比较
left和right指针。更清楚的递归定义是：当前两个节点要相同，左子树要相同，右子树也要相同。空节点要先处理，否则还没开始比较就会访问到不存在的.val。
← Quiz