LeetCode 面试题 04.10. 检查子树

2026-03-28 HGNULB 约 8 分钟

文章信息 3 个分类 5 个标签

分类

题目描述

✅ 面试题 04.10. 检查子树

题意分析

给两棵二叉树 t1 和 t2，判断 t2 是不是 t1 的子树。这里的子树是严格意义的：必须存在 t1 中的某个节点，以它为根向下的整棵结构与 t2 逐节点完全一致——形状相同、对应位置的值也相同，而且不能只匹配 t2 的一部分。

「以某节点为根的整棵结构」这句话拆出两个层次：先要在 t1 里找到候选的起点，再要判断从这个起点开始两棵树是否处处相同。两件事的粒度不同，前者是遍历，后者是比对，混在一个递归里必然出错，所以自然要写成两个函数。

题面还提示 t1 可能非常大（节点数可达百万级）而 t2 相对小。这个规模差是重要信号：它说明朴素的「每个节点都完整比一遍」在最坏情况下会退化，也预告了进阶解法的方向。

边界：t2 为空时按约定返回真——空树是任何树的子树；t1 为空而 t2 非空必然为假；两个节点值相等但孩子结构不同，不算匹配；t2 的值序列在 t1 中出现但深度位置不同，也不算。

解法：深度优先搜索

核心思路

先把问题拆成一个更小的、已经会做的问题：判断两棵树是否完全相同。这个子问题的递归很直白——根值相等且左子树相同且右子树相同。有了它，原问题就变成「在 t1 中找一个节点，使得以它为根的子树与 t2 完全相同」。

于是形成双层递归：外层 checkSubTree 负责在 t1 上枚举起点，内层 dfs 负责从给定起点做逐点比对。外层在每个节点上先调一次内层试试，成了就立刻返回真，没成就把问题递归地丢给左右孩子——只要 t1 的任意一个节点匹配成功，整体就成立，所以外层用的是或的关系。

内层比对的递归基必须写得非常克制，这是本题最容易翻车的地方。正确的语义是：dfs(a, b) 判断以 a、b 为根的两棵树是否完全相同。所以 b 为空时，a 也必须为空才算相同（写成无条件返回真就会把「t2 提前结束」误判成匹配）；b 非空而 a 为空，或者两者值不等，都直接返回假；其余情况递归比对左右两侧，用与连接。

两层的空判语义必须区分清楚：外层的 t2 == null 返回真，说的是「空树是任何树的子树」；内层的 b == null 要求 a == null，说的是「两棵树在这一位置必须同时结束」。同一个空判在两个函数里含义相反，把它们写混是本题的头号错误来源。

解题步骤

外层先处理两个空：t2 为空返回真（空树是子树），t1 为空且 t2 非空返回假。顺序不能反——先判 t2 才能让「两者皆空」也落到真上。

外层先试当前节点：调用 dfs(t1, t2)，成功就立即返回真，不再往下找。这是一次剪枝，也让「根就匹配」的常见情形只花一次比对。

外层递归两个孩子：checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2)。用或短路，左边找到就不搜右边。注意递归的是外层函数而不是内层比对函数——外层换起点，内层不换。

内层的三条递归基：b 为空时返回 a == null；a 为空或值不等时返回假；这两条覆盖了所有提前终止的情形。

内层同步下降：dfs(a.left, b.left) && dfs(a.right, b.right)。必须左对左、右对右，且用与连接——结构相同要求每一处都相同。

以 t1 = [3, 4, 5, 1, 2]（根 3，左孩子 4 带孩子 1、2，右孩子 5）、t2 = [4, 1, 2] 走一遍。

外层从根 3 开始：dfs(3, 4) 值不等，立刻返回假。于是递归左孩子：checkSubTree(4, t2) 里调 dfs(4, 4)——值相等，继续比 dfs(1, 1) 与 dfs(2, 2)，两者各自再往下比时 b 为空且 a 也为空，返回真；于是 dfs(4, 4) 返回真，外层立即返回真，右子树 5 那一支根本没被访问。答案为真。

再看反例 t1 = [3, 4, 5, 1, 2, null, null, null, null, 0]（在节点 2 下面多挂一个孩子 0）、t2 仍是 [4, 1, 2]。外层走到节点 4 时 dfs(4, 4) 继续下降到 dfs(2, 2)：值相等，再比左孩子 dfs(0, null)——此时 b 为空而 a 是节点 0，按递归基返回 a == null 即假，整条与链坍塌，dfs(4, 4) 返回假。外层继续搜 1、2、0、5 各点均不匹配，最终返回假。若把内层的 b == null 写成无条件返回真，这个用例就会被错误地判成真——t2 只是 t1 的一部分，而不是完整子树。

代码实现

class Solution {
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if (t2 == null) {
            // 空树是任何树的子树。
            return true;
        }
        if (t1 == null) {
            return false;
        }
        if (dfs(t1, t2)) {
            return true;
        }
        // 换个起点接着找。
        return checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
    }

    // 判断以 t1、t2 为根的两棵树是否完全相同。
    private boolean dfs(TreeNode t1, TreeNode t2) {
        if (t2 == null) {
            // 这里必须要求 t1 同时结束，否则会把「匹配一部分」当成成功。
            return t1 == null;
        }
        if (t1 == null || t1.val != t2.val) {
            return false;
        }
        return dfs(t1.left, t2.left) && dfs(t1.right, t2.right);
    }
}

func checkSubTree(t1 *TreeNode, t2 *TreeNode) bool {
    // 判断以 t1、t2 为根的两棵树是否完全相同。
    var dfs func(t1, t2 *TreeNode) bool
    dfs = func(t1, t2 *TreeNode) bool {
        if t2 == nil {
            // 这里必须要求 t1 同时结束，否则会把「匹配一部分」当成成功。
            return t1 == nil
        }
        if t1 == nil || t1.Val != t2.Val {
            return false
        }
        return dfs(t1.Left, t2.Left) && dfs(t1.Right, t2.Right)
    }

    if t2 == nil {
        // 空树是任何树的子树。
        return true
    }
    if t1 == nil {
        return false
    }
    if dfs(t1, t2) {
        return true
    }
    // 换个起点接着找。
    return checkSubTree(t1.Left, t2) || checkSubTree(t1.Right, t2)
}

复杂度分析

时间复杂度：$O(nm)$ 最坏，n、m 分别是两棵树的节点数。外层最多在 n 个起点上各触发一次内层比对，单次比对最坏要走完 m 个节点；实际运行远快于上界，因为绝大多数起点在根值不等时就立刻失败。

空间复杂度：$O(h_1 + h_2)$，两层递归的栈深度之和，h 为对应树高。没有使用任何额外容器，树退化成链时为 $O(n + m)$。

关键点总结

把「找子树」拆成「枚举起点」加「判两树相同」两个函数，是这类题的标准结构；一旦试图用一个递归同时干两件事，空判语义就会打架。

同一个空判在两层里含义相反：外层的「t2 为空返回真」是题目约定，内层的「t2 为空要求 t1 也为空」是结构相等的定义；面试中主动点破这个区别，基本就答到了考官的得分点上。

外层用或、内层用与，对应「任一起点成功即可」与「处处相同才算相同」两种逻辑关系，写反任何一个都会得到相反的答案。

短路求值在这里是有意为之的剪枝：外层找到即停，内层一处不符即停，让最坏复杂度在实际数据上很难被触发。

面试官给出「t1 有百万节点」这类规模时，期待的进阶答案是序列化加字符串匹配：把两棵树按前序序列化（空孩子必须用占位符，否则不同结构会得到相同串），再用 KMP 在 t1 的串里找 t2 的串，把时间压到 $O(n + m)$；也可以用子树哈希做同样的事。能主动给出这条路径，是这道题与 572 的主要区别。

易错点总结

内层 t2 == null 无条件返回真：t1 = [3, 4, 5, 1, 2, null, null, null, null, 0]、t2 = [4, 1, 2] → 节点 2 下面多出来的 0 不再被检查，把「匹配了一部分」误判为子树。

内层漏判 t1 == null：t1 = [1, 2]、t2 = [1, 2, 3] → 比到 t1 的空右孩子时访问 t1.val 直接空指针异常。

外层递归调用写成内层函数：t1 = [3, 4, 5, 1, 2]、t2 = [4, 1, 2] → 变成要求 t1 与 t2 从根就完全相同，答案错判为假。

内层递归调用写成外层函数：t1 = [1, 2, 3]、t2 = [1, 2] → 比对时又去子树里换起点找，t2 的右孩子缺失被忽略，非子树被判成真。

内层用或连接左右：t1 = [1, 2, 3]、t2 = [1, 2, 9] → 左侧匹配成功就返回真，右侧的 3 与 9 不等被忽略。

外层用与连接左右孩子：t1 = [3, 4, 5]、t2 = [4] → 要求左右两棵子树都能找到才算成功，答案错判为假。

外层两个空判顺序写反：t1 = null、t2 = null → 先判 t1 为空返回假，而正确答案是真。

比对时左右交叉：dfs(a.left, b.right) → t1 = [1, 2, 3]、t2 = [1, 3, 2] 这类镜像结构被误判为相同，实际上那是对称而非相等。

改用序列化匹配却不给空孩子加占位符：t1 = [1, 2]（只有左孩子）、t2 = [1, null, 2]（只有右孩子）→ 两者前序序列都是 1, 2，结构完全不同却被判成匹配。

序列化时不给数值加分隔符：t2 的序列 1, 2 会匹配到 t1 中的 11, 2 或 1, 22，数字被截断拼接导致误报。

相似题目

题目	难度	考察点
572. 另一棵树的子树	简单	与本题同题，数据规模小，双层递归足以通过
100. 相同的树	简单	只有本题的内层比对部分，是理解结构相等定义的最小样本
101. 对称二叉树	简单	比对时左右交叉下降，正好对照本题「不能交叉」的要求
652. 寻找重复的子树	中等	需要给每棵子树算结构指纹并计数，是本题进阶哈希做法的正面用法
1367. 二叉树中的链表	中等	同样是双层递归，但匹配对象是一条自上而下的路径而非完整子树
面试题 04.08. 首个共同祖先	中等	也在树上做搜索并合并左右结果，返回的是节点而不是布尔