26 树的子结构

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