# 剑指Offer题解 - Day13

# 剑指 Offer 26. 树的子结构

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

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

例如: 给定的树 A:

1
2
3
4
5

给定的树 B：

   4 
  /
 1

1
2
3

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

示例 1：

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

1
2

示例 2：

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

1
2

限制：

0 <= 节点个数 <= 10000

思路：

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

先序遍历树A，获取到每一个子节点；
判断树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))
};

1
2
3
4
5
6
7
8
9
10
11
12
13

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

分析：

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

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

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

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

# 总结

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

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

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

剑指Offer题解 - Day12 剑指Offer题解 - Day14