面试题26_树的子结构.md

面试题 26 ：树的子结构

---

leetcode-cn 题目地址

📗difficulty： Medium

🎯Tags：

• 树

---

1. 题目描述📃

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:

给定的树 A ：

	 3
    / \
   4   5
  / \
 1   2

给定的树 B ：

   4 
  /
 1

限制：

• 0 <= 节点个数 <= 10000

---

2. 解题思路💡

《剑指 Offer》的做法

在 isSubStructure ，尝试寻找到 A 中和 B 相等的“起始点”，如果当前的 A.val != B.val ，就对 A 进行先序遍历，直到找到这样的节点 或者 A 遍历结束，没有找到这样的节点，返回 false。

如果找到了 A.val == B.val 就执行 isContainerSubtree 去检查，是不是完全包含子结构。

贯穿这 2 个递归函数的，是对树的先序遍历，同时，因为涉及到树的操作，需要格外注意空指针的判定，否则容易引起程序崩溃和错误答案。

代码实现

public boolean isSubStructure(TreeNode A, TreeNode B) {
    // 任意一棵 树 为空，返回 false
    boolean res = false;

    if (A != null && B != null) {
        if (A.val == B.val) {
            res = isContainerSubtree(A, B);
        }

        if (!res) {
            res = isSubStructure(A.left, B);
        }

        if (!res) {
            res = isSubStructure(A.right, B);
        }
    }
    return res;
}

public boolean isContainerSubtree(TreeNode base, TreeNode sub) {
    // 这里判断 null 的先后是有原因的，只能允许 sub 为 null
    // 检索完 sub 子树，说明 base 中包含 sub 的子结构
    if (sub == null) {
        return true;
    }

    if (base == null) {
        return false;
    }

    if (base.val != sub.val) {
        return false;
    }

    return isContainerSubtree(base.left, sub.left) && isContainerSubtree(base.right, sub.right);
}

复杂度分析

• 时间复杂度：O(n + m) 。最坏情况下，每个节点都需要被访问一次。
• 空间复杂度：O(n + m) ，树退化为单链表的情况下，为最坏情况。

以下代码来自 leetcode-cn 用户 Krahets 的题解，感谢其的详细讲解和分析。

更加容易理解的一个解答

这里做的改进是将 判定值 的操作放到了 recur 函数中去。思路上更加容易理解。

// 思路二：比较值的操作在 recur 时一并判断
public boolean isSubStructure(TreeNode A, TreeNode B) {
    return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}

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

复杂度分析

• 时间复杂度 O(M * N) ： 其中 M,N 分别为树 A 和 树 B 的节点数量；先序遍历树 A 占用 O(M) ，每次调用 recur(A, B) 判断占用 O(N) 。
• 空间复杂度 O(M) ： 当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M ≤ N 时，遍历树 A 与递归判断的总递归深度为 M ；当 M > N 时，最差情况为遍历至树 A 叶子节点，此时总递归深度为 M。

---

3. 总结🎯

主要考察树的遍历熟悉程度，和对递归条件的把握。使用最简单的 先序遍历的递归形式 即可。

相似题目

面试题55 - I. 二叉树的深度