另一棵树的子树 图解题解

这道题到底在问什么

输入

root=12节点树, subRoot=[4,1,2]

输出

true

最优解：一步一步想明白

1. 3思路拆成两层：① 外层遍历大树每个节点当候选根；② 内层 sameTree(候选, subRoot) 把两棵树同步往下走、逐个比值。下面把这两层都画出来看。
2. 4外层遍历大树 12 个候选根左边是大树（12 个节点），右侧面板是目标子树 4/(1,2)——一个根 4，挂着两个叶子 1 和 2。我们要在大树里找一处和它完全相同的子树。开始按层序一个个试。
3. 5试候选节点 3（橙）。sameTree 第一件事就是比根值：候选根是 3，目标根是 4，3 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
4. 6试候选节点 4（橙）：根值 4 == 4，第一步过了！但「根相同」只是开头，sameTree 要求整棵子树都一样，所以接着同步比对：候选的左孩子 ≟ 目标的左叶 1，候选的右孩子 ≟ 目标的右叶 2。
5. 7比左孩子（蓝）：候选左孩子值 1 == 目标左叶 1，值是对的！可是别急——sameTree 还要往下比：目标里的 1 是叶子（下面没东西），而候选这个 1 底下还挂着 0、8。一边到底了、一边还有孩子，结构对不上 → 整个候选否。
6. 8候选 4 这一支被否，恢复成灰、记为「已排除」（蓝）。注意：值 4 虽然出现了，但它底下的形状和目标不一样——子树匹配看的是整坨结构，不是只看根。继续往后试下一个节点。
7. 9试候选节点 6（橙）。sameTree 第一件事就是比根值：候选根是 6，目标根是 4，6 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
8. 10试候选节点 1（橙）。sameTree 第一件事就是比根值：候选根是 1，目标根是 4，1 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
9. 11试候选节点 2（橙）。sameTree 第一件事就是比根值：候选根是 2，目标根是 4，2 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
10. 12试候选节点 7（橙）。sameTree 第一件事就是比根值：候选根是 7，目标根是 4，7 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
11. 13试候选节点 9（橙）。sameTree 第一件事就是比根值：候选根是 9，目标根是 4，9 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
12. 14试候选节点 0（橙）。sameTree 第一件事就是比根值：候选根是 0，目标根是 4，0 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
13. 15试候选节点 8（橙）。sameTree 第一件事就是比根值：候选根是 8，目标根是 4，8 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
14. 16试候选节点 6（橙）。sameTree 第一件事就是比根值：候选根是 6，目标根是 4，6 ≠ 4，连第一步都过不了，整个候选立刻否决——根值不同，下面再像也没用。
15. 17试候选节点 4（橙）：根值 4 == 4，第一步过了！但「根相同」只是开头，sameTree 要求整棵子树都一样，所以接着同步比对：候选的左孩子 ≟ 目标的左叶 1，候选的右孩子 ≟ 目标的右叶 2。
16. 18比左孩子（蓝）：候选左孩子 1 == 目标左叶 1，而且它也是叶子（下面没孩子），和目标里的 1 完全对应 ✓。左边过了，再看右边。
17. 19比右孩子（蓝）：左边虽然过了，但候选右孩子是 5，目标右叶是 2，5 ≠ 2，对不上 → 本候选否。只差一个值，整坨就不算相同。
18. 20候选 4 因右子不匹配被否，记为「已排除」（蓝）。哪怕根和左边都对上，只要有一处不同，整棵子树就不算相同。继续往后试。
19. 21试候选节点 4（橙）：根值 4 == 4，第一步过了！但「根相同」只是开头，sameTree 要求整棵子树都一样，所以接着同步比对：候选的左孩子 ≟ 目标的左叶 1，候选的右孩子 ≟ 目标的右叶 2。
20. 22比左孩子（蓝）：候选左孩子 1 == 目标左叶 1，而且它也是叶子（下面没孩子），和目标里的 1 完全对应 ✓。左边过了，再看右边。
21. 23比右孩子（蓝）：候选右孩子 2 == 目标右叶 2，也是叶子，完全对应 ✓。至此：根 4==4、左 1==1（叶）、右 2==2（叶），两棵树逐节点全部相同 → sameTree 成立，找到子树了！
22. 24sameTree(节点4, subRoot) = true命中！以候选 4 为根的整棵子树（绿色这一坨）—— 根 4、左叶 1、右叶 2 —— 和目标 subRoot 一模一样。题目只问「是不是子树」，找到一处即可返回 true，外层遍历就此停止。
23. 25命中根 = 节点4回顾整趟：我们把大树每个节点都当候选根试了一遍，绝大多数在「比根值」那一步就被刷掉；两个值为 4 的候选里，一个因为孩子下面结构更深被否，另一个（绿色 path 这坨）逐节点全对 → subRoot 是 root 的子树，返回 true。

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

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);
    }
}

class Solution:
    def isSubtree(self, root, subRoot):
        if not root:                       # 走到空都没匹配上
            return False
        if self.same(root, subRoot):       # 以当前节点为根试匹配
            return True
        return (self.isSubtree(root.left, subRoot)
                or self.isSubtree(root.right, subRoot))
    def same(self, a, b):
        if not a and not b:                # 都空 → 相同
            return True
        if not a or not b:                 # 一空一非空 → 不同
            return False
        if a.val != b.val:                 # 值不等 → 不同
            return False
        return self.same(a.left, b.left) and self.same(a.right, b.right)

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) return false;                     // 走到空都没匹配上
        if (sameTree(root, subRoot)) return true;    // 以当前节点为根试匹配
        return isSubtree(root->left, subRoot)
            || isSubtree(root->right, subRoot);
    }
    bool sameTree(TreeNode* a, TreeNode* b) {
        if (!a && !b) return true;                   // 都空 → 相同
        if (!a || !b) return false;                  // 一空一非空 → 不同
        if (a->val != b->val) return false;          // 值不等 → 不同
        return sameTree(a->left, b->left)
            && sameTree(a->right, b->right);
    }
};

复杂度

面试官可能追问