LeetCode 剑指 Offer 26. 树的子结构

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

题目描述

✅ 剑指 Offer 26. 树的子结构

image-20261001230752549

题意分析

判断非空树 B 是否能从树 A 的某个节点开始完整匹配：B 中每个节点的值，以及对应的左、右孩子关系，都必须在 A 中找到。

匹配不能跳过中间节点，也不能交换左右孩子。B 某个方向没有节点时，不再要求 A 的对应位置为空，因此 A 可以在已匹配结构之外继续有额外孩子；这与要求整棵子树完全相同不同。题目另有约定：空树不是任何树的子结构，所以空 B 必须返回 false。

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

核心思路

[!blue]

需要分开解决两个问题：在 A 中从哪里开始匹配，以及起点确定后能否覆盖整个 B。若把寻找起点和结构匹配混在一起，就容易在匹配过程中跳过不相等节点，错误接受不连续的结构。

外层 isSubStructure(A, B) 负责寻找起点。先尝试从当前 A 节点匹配完整的 B；若失败，再去 A 的左子树、右子树寻找。三个候选位置只要有一个成功即可，因此用 || 连接。每换一个起点，B 都从原来的根开始，不能跟着向下移动。

内层 match(a, b) 负责固定起点后的对应匹配，返回“以 a 为起点能否覆盖以 b 为根的全部结构”。它有三个判断：

  • b 为空：当前方向已经没有需要匹配的目标，返回 true，不再检查 a 是否还有额外节点。
  • b 非空，但 a 为空或值不同：目标节点缺失或不匹配，返回 false。
  • 两者非空且值相同：继续匹配对应的左右孩子，两支都成功才返回 true，因此使用 &&。

外层拒绝空 B，内层却接受空 b，两者并不矛盾：外层检查的是题目是否提供了合法的目标树，内层表示非空目标的某一支已经匹配完成。内层要先判断 b，这样两者同时为空时也会正确判为该分支匹配成功。

外层枚举了 A 的所有可能起点，内层又要求 B 的每条必要连接都逐一对应，所以只要存在子结构就能找到，也不会把仅有部分节点相同的情况当成成功。

解题步骤

  1. 主函数中，若 A 或 B 为空，返回 false。
  2. 尝试在当前 A 节点调用 match(A, B)；失败后，分别递归到 A 的左右子树，始终保留完整的 B。
  3. match 先判断 b 是否为空，为空直接返回 true。
  4. 若 b 非空而 a 为空或节点值不同，返回 false。
  5. 否则同步匹配左右孩子，只有两个方向都成功才返回 true。

代码实现

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) {
        // 固定起点的匹配中，目标结构用完即成功，必须先于 a 判空。
        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 {
    // 固定起点的匹配中，目标结构用完即成功，必须先于 a 判空。
    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)
}

复杂度分析

设 $A$、$B$ 的节点数分别为 $m$、$n$，$A$ 的高度为 $h_A$。

  • 时间复杂度：最坏为 $O(mn)$。最多尝试 $A$ 的每个节点作为起点，每次匹配最多检查 $B$ 的全部节点。
  • 辅助空间复杂度：$O(h_A)$。寻找起点与固定起点后的匹配都沿着 $A$ 的父子路径深入，同时存在的递归调用总深度受 $A$ 的高度限制；退化成链时为 $O(m)$。

关键点总结

[!green]

  • 外层枚举起点用 ||，内层要求两支同时对应则用 &&。
  • 外层移动 A 时保持 B 的根不变，内层才同步移动两棵树的对应孩子。
  • B 的某一支匹配完即可成功，不要求 A 的对应分支同时结束。

易错点总结

[!yellow]

  • 主函数把空 B 判为成功，会违反“空树不是任意树的子结构”的题目约定。
  • 内层先把空 a 判为失败，会在 a、b 同时为空时误判，应优先处理空 b。
  • 外层搜索起点时连 B 也一起向下移动，会丢失目标根，只匹配到 B 的一部分。
  • 内层用 || 连接左右匹配，会把只匹配一边的情况接受；目标要求的两边都必须存在并对应。
  • 只在 A 的根尝试一次，会漏掉更深处的起点；固定起点后跳过不匹配节点，又会错误接受不连续的结构。

相似题目

题目 难度 关联与区别
572. 另一棵树的子树 简单 原题要求完整子树结构相同，本题模式结束后可以忽略大树额外的孩子，匹配终止条件不同。
100. 相同的树 简单 原题左右两树必须同步结束，本题只需小模式被完整匹配，不能直接替换为相同树判定。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/85666181
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！