LeetCode 剑指 Offer 26. 树的子结构

约 5 分钟
文章信息 13 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 50-100 字节跳动 微软 美团 阿里巴巴 腾讯 猿辅导 剑指 Offer 剑指 Offer（第 2 版）
标签
深度优先搜索 树 二叉树 二叉树经典题
目录

题目描述

✅ 剑指 Offer 26. 树的子结构

image-20241107205339686

image-20250418234136559

题意分析

给定两棵二叉树 A 和 B，问 B 是不是 A 的「子结构」。这里的子结构指：能在 A 中找到某个节点，从它开始按照 B 的形状一层层往下对照，B 里每个节点都能在 A 的对应位置找到一个值相同的节点。

必须分清「子结构」和「子树」的差别，这是本题最容易读错的地方。子树要求从某个节点起完整地一模一样，A 那一块不能多出任何节点；而子结构只要求 B 被「覆盖」住，A 在 B 的叶子下面还可以继续挂节点，也可以在匹配路径旁边有别的分支。换句话说，B 匹配完了就算成功，不必追问 A 还剩什么。

题目还给了一条硬性约定：空树不是任何树的子结构。所以只要 B 为空就必须返回 false，A 为空同样返回 false。这条约定和递归内部「b 走到空表示匹配成功」的判断在语义上正好相反，是本题第二个坑。

需要考虑的边界：A 为空、B 为空、两者都为空；B 只有一个节点；B 的节点数大于 A；A 中存在多个值与 B 根相同的节点，前面几个匹配失败但后面某个能成功；节点值允许重复出现。

解法：枚举起点 + 递归匹配结构

核心思路

问题关键：子结构不要求 A 的匹配区域与 B 完全相同；B 匹配结束后，A 仍可有额外节点。因此不能直接套用「判断两棵树相同」的递归出口。

为什么用两层递归：B 的根可能对应 A 的任意节点。外层 isSubStructure 枚举 A 中的匹配起点，内层 match 在起点确定后同步比较两棵树，职责分开后边界最清楚。

状态定义与正确性：match(a, b) 表示 B 从 b 开始的结构能否被 A 从 a 开始覆盖。b == null 说明 B 已匹配完，返回 true；a == null 或值不同则返回 false；否则左右分支都要匹配。外层依次检查当前节点、左子树和右子树，覆盖了 A 中所有可能起点。

解题步骤

  1. 主函数先处理题目约定：A 或 B 为空时返回 false。
  2. 在 A 的当前节点调用 match(A, B)；成功就直接返回 true。
  3. 当前起点失败时，分别到 A 的左右子树继续寻找，B 始终从根开始匹配。
  4. match 中先判断 b == null，再判断 a == null 或值不同，最后递归匹配左右孩子。

例如 A = [3,4,5,1,2]、B = [4,1]：根节点 3 匹配失败，移动到节点 4 后，4 和左孩子 1 均匹配；B 的右支为空，即使 A 对应位置有节点 2 也不影响结果。

代码实现

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return match(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean match(TreeNode a, TreeNode b) {
        if (b == null) {
            return true;
        }
        if (a == null || a.val != b.val) {
            return false;
        }

        // B 的每个节点都要在 A 的对应位置匹配。
        return match(a.left, b.left) && match(a.right, b.right);
    }
}

func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if A == nil || B == nil {
        return false
    }
    return matchTree(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func matchTree(a *TreeNode, b *TreeNode) bool {
    if b == nil {
        return true
    }
    if a == nil || a.Val != b.Val {
        return false
    }

    // 从当前起点继续匹配 B 的左右结构。
    return matchTree(a.Left, b.Left) && matchTree(a.Right, b.Right)
}

复杂度分析

  • 时间复杂度：最坏为 $O(mn)$，其中 m、n 分别是 A、B 的节点数；A 的每个节点都可能触发一次最多 $O(n)$ 的匹配。
  • 空间复杂度：$O(h_A)$，递归栈深度受 A 的高度限制；退化成链时为 $O(m)$。

关键点总结

  • 外层负责枚举起点，内层负责固定起点后的结构匹配。
  • 外层递归时 B 不动；内层递归时 A、B 的左右指针同步下降。
  • b == null 必须优先判成功，这体现「B 被覆盖完即可」。
  • 与「子树」不同，本题允许 A 在 B 匹配结束的位置继续存在子节点。

易错点总结

  • 主函数把空 B 判为 true：违反题目「空树不是任意树的子结构」的约定。
  • match 先判断 a == null：当 a、b 同时为空时会误判，必须先处理 b == null。
  • 外层递归把 B 也向下移动：会丢掉 B 的根；每换一个 A 的起点，都应重新匹配完整的 B。
  • 内层左右结果使用 ||：B 有两个孩子而 A 只匹配一边时也会误判成功，必须使用 &&。
  • 只在 A 的根调用一次 match：会漏掉 B 出现在 A 子树中的情况。

相似题目

题目 难度 考察点
572. 另一棵树的子树 简单 同为双层递归，但内层要求完全相同，出口必须是 a 与 b 同时为空才算成功；且空树在该题中被视为合法子树，与本题约定相反
面试题 04.10. 检查子树 中等 判定标准与 572 一致而非本题，考点转向大规模数据下的优化，可用序列化后做字符串匹配，本题的覆盖式定义则无法这样转化
100. 相同的树 简单 只有本题内层这一层递归，没有枚举起点的外层，两棵树的根天然对齐，是本题内层函数的纯粹版本
437. 路径总和 III 中等 同样是「外层枚举起点、内层从起点向下」的双层递归骨架，但内层沿路径累加求和并统计数量，返回的是计数而非布尔
101. 对称二叉树 简单 也是双参数同步下降的递归，但两个指针以镜像方式配对（左配右、右配左），比较的是同一棵树的两侧而非两棵不同的树