题目描述
思路解析动画文字版
思路拆成两层：① 外层遍历大树每个节点当候选根；② 内层 sameTree(候选, subRoot) 把两棵树同步往下走、逐个比值。下面把这两层都画出来看。
准备 · 两棵树：左边是大树（12 个节点），右侧面板是目标子树 4/(1,2)——一个根 4，挂着两个叶子 1 和 2。我们要在大树里找一处和它完全相同的子树。开始按层序一个个试。
试候选节点 3（橙）。sameTree 第一件事就是比根值：候选根是 3，目标根是 4，3 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 4（橙）：根值 4 == 4，第一步过了！但「根相同」只是开头，sameTree 要求整棵子树都一样，所以接着同步比对：候选的左孩子 ≟ 目标的左叶 1，候选的右孩子 ≟ 目标的右叶 2。
比左孩子（蓝）：候选左孩子值 1 == 目标左叶 1，值是对的！可是别急——sameTree 还要往下比：目标里的 1 是叶子（下面没东西），而候选这个 1 底下还挂着 0、8。一边到底了、一边还有孩子，结构对不上 → 整个候选否。
候选 4 这一支被否，恢复成灰、记为「已排除」（蓝）。注意：值 4 虽然出现了，但它底下的形状和目标不一样——子树匹配看的是整坨结构，不是只看根。继续往后试下一个节点。
试候选节点 6（橙）。sameTree 第一件事就是比根值：候选根是 6，目标根是 4，6 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 1（橙）。sameTree 第一件事就是比根值：候选根是 1，目标根是 4，1 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 2（橙）。sameTree 第一件事就是比根值：候选根是 2，目标根是 4，2 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 7（橙）。sameTree 第一件事就是比根值：候选根是 7，目标根是 4，7 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 9（橙）。sameTree 第一件事就是比根值：候选根是 9，目标根是 4，9 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 0（橙）。sameTree 第一件事就是比根值：候选根是 0，目标根是 4，0 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 8（橙）。sameTree 第一件事就是比根值：候选根是 8，目标根是 4，8 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 6（橙）。sameTree 第一件事就是比根值：候选根是 6，目标根是 4，6 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
试候选节点 4（橙）：根值 4 == 4，第一步过了！但「根相同」只是开头，sameTree 要求整棵子树都一样，所以接着同步比对：候选的左孩子 ≟ 目标的左叶 1，候选的右孩子 ≟ 目标的右叶 2。
比左孩子（蓝）：候选左孩子 1 == 目标左叶 1，而且它也是叶子（下面没孩子），和目标里的 1 完全对应 ✓。左边过了，再看右边。
比右孩子（蓝）：左边虽然过了，但候选右孩子是 5，目标右叶是 2，5 ≠ 2，对不上 → 本候选否。只差一个值，整坨就不算相同。
候选 4 因右子不匹配被否，记为「已排除」（蓝）。哪怕根和左边都对上，只要有一处不同，整棵子树就不算相同。继续往后试。
试候选节点 4（橙）：根值 4 == 4，第一步过了！但「根相同」只是开头，sameTree 要求整棵子树都一样，所以接着同步比对：候选的左孩子 ≟ 目标的左叶 1，候选的右孩子 ≟ 目标的右叶 2。
比左孩子（蓝）：候选左孩子 1 == 目标左叶 1，而且它也是叶子（下面没孩子），和目标里的 1 完全对应 ✓。左边过了，再看右边。
比右孩子（蓝）：候选右孩子 2 == 目标右叶 2，也是叶子，完全对应 ✓。至此：根 4==4、左 1==1（叶）、右 2==2（叶），两棵树逐节点全部相同 → sameTree 成立，找到子树了！
命中 · 子树存在：命中！以候选 4 为根的整棵子树（绿色这一坨）—— 根 4、左叶 1、右叶 2 —— 和目标 subRoot 一模一样。题目只问「是不是子树」，找到一处即可返回 true，外层遍历就此停止。
答案 · 是子树 (true)：回顾整趟：我们把大树每个节点都当候选根试了一遍，绝大多数在「比根值」那一步就被刷掉；两个值为 4 的候选里，一个因为孩子下面结构更深被否，另一个（绿色 path 这坨）逐节点全对 → subRoot 是 root 的子树，返回 true。
参考代码
class Solution { public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) return false; // 走到空都没匹配上 if (sameTree(root, subRoot)) return true; // 以当前节点为根试匹配 return isSubtree(root.left, subRoot) // 否则去左右子树继续找 || isSubtree(root.right, subRoot); } private boolean sameTree(TreeNode a, TreeNode b) { if (a == null && b == null) return true; // 都空 → 相同 if (a == null || b == null) return false; // 一空一非空 → 不同 if (a.val != b.val) return false; // 值不等 → 不同 return sameTree(a.left, b.left) // 左==左 且 右==右 && sameTree(a.right, b.right); }}复杂度
- 时间：O(m·n)，m=大树节点数，n=子树节点数；最坏每个候选都比对到底
- 空间：O(max(h, k))，两层递归栈，h=大树高、k=子树高
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉搜索树的最近公共祖先
LeetCode 235 · 中等 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题