剑指Offer题解 - Day13

「剑指 Offer 26. 树的子结构」

力扣题目链接[1]

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

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

例如: 给定的树 A:

     3
    / \
   4   5
  / \
 1   2

给定的树 B：

   4 
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

思路：

判断树 B 是否为树 A 的子结构，也就意味着树 B 的根节点可能是树 A 的任意一个子节点。因此我们可以通过两个步骤来判断：

1. 先序遍历树 A，获取到每一个子节点；
2. 判断树 A 中，以每一个遍历到的子节点为根节点的子树是否包括树 B。

递归

/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
const recur = (A, 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);
}
const isSubStructure = (A, B) => {
    return (A !== null && B !== null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B))
};

• 「时间复杂度 O(mn)」。
• 「空间复杂度 O(m)」。

分析：

首先，递归的作用是用来判断：树 A 和树 B 是否是包含的关系。具体逻辑如下：

1. 当树 B 为空，则意味着已经遍历完所有的节点，树 A 是包含树 B 的，返回true。
2. 当树 A 为空，则意味着已遍历完树 A 所有节点，但是树 B 依旧有节点，因此树 A 不包含树 B，返回false。
3. 当树 A 和树 B 节点值不同时，意味着不是包含关系，返回false。
4. 上述条件也是递归的终止条件。
5. 继续递归 A、B 的左右子树，并返回。通过&&操作符可以在回溯的时候起到短路运算的目的，提前返回。

判断是否是子结构的逻辑如下：

1. 根据题意，空树不是任意一个树的子结构。因此先决条件是 A 和 B 都不为空。
2. 满足上述条件后，再判断树 A 是否包含树 B。
3. 或者是 A 的左子树是否包含树 B；或者是 B 的右子树是否包含树 B。
4. 实质上，上面两个步骤是对树 A 进行先序遍历。
5. 同样的，利用了递归处理。使用||运算符使得回溯时起到短路运算的目的，提前返回。

总结

本题利用了递归的思想进行题解。使用递归一定要注意递归的终止条件，否则很容易造成死循环。

同时利用短路运算的特性，在递归回溯的时候避免额外的计算其他分支。

复杂度方面：遍历树 A 的时候，嵌套遍历树 B 的节点，因此时间复杂度是O(mn)。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dshwe/