树的子结构

题目

题目来源：力扣（LeetCode）

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

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

例如:
给定的树 A:

 3<br />    / \<br />   4   5<br />  / \<br /> 1   2<br />给定的树 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 的任意一个节点。因此，判断 树B 是否是 树A 的子结构，需完成以下两步工作：

1. 先序遍历 树A 中的每个节点 nA ；对应的函数为：isSubStructure(A, B)
2. 判断 树A 中以 nA 为根节点的子树 是否包含 树B ，对应的函数为：recur(A, B)

我们先来分析下 recur(A, B) 函数：

终止条件：
当树B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true；
当 树A 为空：说明已经越过树 A 的叶子节点，即匹配失败，返回 false；
当树A 的根节点 和 树B 的根节点的值不同：说明匹配失败，返回 false；

返回值：
判断 树A 和 树B 的左子节点是否相等，即 recur(A.left, B.left)；
判断 树A 和 树B 的右子节点是否相等，即 recur(A.right, B.right)；

我们接下来再看 isSubStructure(A, B) 函数：

特例处理： 当 树A为 空 或 树B 为空时，直接返回 false；
返回值： 若 树B 是树A 的子结构，则必满足以下三种情况之一，因此用或 || 连接：

1. 以 节点A 为根节点的子树 包含树B ，对应 recur(A, B)；
2. 树B 是 树A 左子树 的子结构，对应 isSubStructure(A.left, B)；
3. 树B 是 树A 右子树 的子结构，对应 isSubStructure(A.right, B)；

以上 2. 3. 实质上是在对树 AA 做 先序遍历 。

const isSubStructure = function (A, B) {
  return (!!A && !!B) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B))
}
const recur = function(A, B) {
  // 树B 为空
  if (B == null) return true;
  // 树A 为空 或者 树A 的树B 的根节点的值不相等
  if (A == null || A.val != B.val) return false;
  // 判断树A 和 树B 的左子节点是否相等，并判断树A 和 树B 的右子节点是否相等
  return recur(A.left, B.left) && recur(A.right, B.right);
}