侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

26 树的子结构

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 149 阅读 / 1,197 字 / 正在检测是否收录...

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。

解题思路:

如果 $B$ 是 $A$ 的子结构,则 $B$ 的根节点可能是 $A$ 中的任意一节点,因此需要遍历A 的所有节点 $nA$,判断 B 是否是 $nA$ 的子结构。

  1. 先序遍历 $A$ 的每个节点 $nA$;
  2. 如果 $A$ 和 $B$ 都为 $null$,根据题意直接返回 $false$。
  3. 判断以 $nA$ 为根节点的树是否包含树 $B$。
    1. 如果 $B$ 为 $null$,那么检查完毕,返回 $true$。
    2. 如果 $A$ 为 $null$ 或者 $A$、$B$ 的值不相等,那么 $B$ 肯定不是子结构,返回 $false$。
    3. 检查 $B$ 的左子树 是否为 $nA$ 的左子树的子结构,并且检查 $B$ 的右子树是否为 $nA$ 的右子树的子结构。

代码:

public boolean isSubStructure(TreeNode A, TreeNode B) {
    return (A != null && B != null)
            && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}

private boolean recur(TreeNode nA, TreeNode B) {
    if (B == null) {
        return true;
    }
    if (nA == null || nA.val != B.val) {
        return false;
    }
    return recur(nA.left, B.left) && recur(nA.right, B.right);
}

复杂度分析

  • 时间复杂度$O(MN)$:其中 $M$ 和 $N$ 分别为 $A$ 树和 $B$ 树的数量。先序遍历 $A$ 树占用 $O(M)$,每次调用 recur 最多占用 $O(N)$。

  • 空间复杂度$O(M)$:当树 $A$ 和树 $B$ 都退化为链表时,递归调用深度最大。当 $M \leq N$ 时,遍历树 $A$ 与递归判断的总递归深度为 $M$ ;当 $M>N$ 时,最差情况为遍历至树 $A$ 叶子节点,此时总递归深度为 $M$。

0

评论区