题目描述
思路解析动画文字版
把判断「两棵树相同」拆成同步递归：每一步同时看两棵树的同一个位置。当前两节点值相同，且它们的左子树相同，且它们的右子树相同——三个条件都满足，才算这一支相同。下面用两棵真的一样的树，逐对走一遍。
准备 · 两棵树并排：先看清布局：把两棵树并排画——左半边是树 p、右半边是树 q（顶上的「相同?」只是个标记，不参与比较）。接下来从两个根节点出发，同位置一对一对地比，看看它们是不是真的完全一样。
比较这一对 · A:1 ↔ B:1：同步递归来到这一对：左树的 1 对上右树同一位置的 1。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：1 和 1 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
比较这一对 · A:2 ↔ B:2：同步递归来到这一对：左树的 2 对上右树同一位置的 2。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：2 和 2 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
比较这一对 · A:4 ↔ B:4：同步递归来到这一对：左树的 4 对上右树同一位置的 4。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：4 和 4 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
比较这一对 · A:8 ↔ B:8：同步递归来到这一对：左树的 8 对上右树同一位置的 8。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：8 和 8 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
8 的左孩子：空 vs 空 · 一致 ✓：顺着节点 8 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
8 的右孩子：空 vs 空 · 一致 ✓：顺着节点 8 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
4 的右孩子：空 vs 空 · 一致 ✓：顺着节点 4 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
比较这一对 · A:5 ↔ B:5：同步递归来到这一对：左树的 5 对上右树同一位置的 5。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：5 和 5 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
5 的左孩子：空 vs 空 · 一致 ✓：顺着节点 5 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
5 的右孩子：空 vs 空 · 一致 ✓：顺着节点 5 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
比较这一对 · A:3 ↔ B:3：同步递归来到这一对：左树的 3 对上右树同一位置的 3。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：3 和 3 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
比较这一对 · A:6 ↔ B:6：同步递归来到这一对：左树的 6 对上右树同一位置的 6。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：6 和 6 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
比较这一对 · A:9 ↔ B:9：同步递归来到这一对：左树的 9 对上右树同一位置的 9。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：9 和 9 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
9 的左孩子：空 vs 空 · 一致 ✓：顺着节点 9 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
9 的右孩子：空 vs 空 · 一致 ✓：顺着节点 9 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
6 的右孩子：空 vs 空 · 一致 ✓：顺着节点 6 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
比较这一对 · A:7 ↔ B:7：同步递归来到这一对：左树的 7 对上右树同一位置的 7。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
值相同 ✓ · 继续比左右子树：7 和 7 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
7 的左孩子：空 vs 空 · 一致 ✓：顺着节点 7 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
7 的右孩子：空 vs 空 · 一致 ✓：顺着节点 7 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空 正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
答案 · 两棵树相同 = true：所有同位置的对都比完了：每一对的值都相等，所有空位也都「空对空」对上。三个条件（值同 + 左子树同 + 右子树同）一路成立，递归层层回传 true——两棵树相同，答案 = true。
边界都落在「出口」上：两棵空树相同（true）；一空一非空在根就 false；哪怕所有值都一样，只要有个孩子挂错了左右位置，同步递归走到那一对就会「一边有、一边空」而返回 false。
参考代码
class Solution { public boolean isSameTree(TreeNode p, TreeNode 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(n)，n=较小树的节点数；最多把每对节点比一次
- 空间：O(h)，递归栈深 = 树高 h；最坏(链)O(n)，平衡 O(log n)
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
另一棵树的子树
LeetCode 572 · 简单 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题