LeetCode 面试题 04.10. 检查子树

约 4 分钟
文章信息 3 个分类 5 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
深度优先搜索 树 二叉树 哈希函数 字符串匹配

题目描述

✅ 面试题 04.10. 检查子树

image-20260929004950507

题意分析

判断 t1 中是否存在一个节点，以它为根的整棵子树与 t2 的结构和节点值完全一致。匹配部分不能多出或少掉孩子；这里约定空 t2 是任意树的子树，返回 true。

解法：枚举根位置并完整比较子树

核心思路

[!blue]

如果 t2 确实是一棵子树，它的根一定对应 t1 中的某个节点。因此外层遍历 t1 的所有可能根位置，内层判断从这个固定起点开始，两棵树是否完全相同。

内层 dfs(t1, t2) 不允许跳过节点：两边都为空才表示这个位置匹配；只空一边表示结构不同；两边都非空时必须值相等，并且左子树、右子树都完整匹配。用 && 合并两侧，才能保证整棵子树一致。

外层先尝试当前 t1 节点。若完整匹配成功，直接返回；否则答案仍可能在它的左子树或右子树中，所以用 || 继续搜索。当前候选失败不代表整棵大树都失败，只有所有候选都不能匹配时才返回 false。

两层函数对空树的判断不同，是因为职责不同：外层是在问「空模式是否能作为子树」，答案为真；内层是在问「这两个固定位置是否完全相同」，必须要求两边同时结束，否则会把只匹配到一部分的结构误判为成功。

解题步骤

  1. t2 为空则成功，t1 为空且 t2 非空则失败。
  2. 以当前 t1 为根调用完整比较函数。
  3. 若失败，分别以 t1 的左右孩子继续寻找候选根。

外层先判断 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 个候选根，每次完整比较需要 $O(m)$。
  • 空间复杂度：$O(h_1+h_2)$，外层寻找候选与内层比较的递归栈叠加，h_1、h_2 为两树高度。

关键点总结

[!green]

外层的「或」枚举可能根位置，内层的「与」验证完整结构；不能把换起点的搜索规则混进固定起点的匹配规则。

易错点总结

[!yellow]

  • 不能在 t2 结束时无条件成功，否则会接受 t1 多出来的孩子。
  • 只比较遍历值而不记录空位，可能混淆不同结构。
  • 左右子树都要完整匹配，不能用或连接内层比较。

相似题目

题目 难度 关联与区别
100. 相同的树 简单 直接复用判断两树完全相同的函数，外层再枚举大树中的候选根。
剑指 Offer 26. 树的子结构 中等 子结构匹配允许大树在模式结束处继续延伸，本题要求整棵子树恰好相同，终止条件不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/18868642
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！