26 树的子结构

Lin2J
2021-07-21 / 0 评论 / 121 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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$。