判断树B是否是A树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
思路：
1、
- 先序遍历树 A中的每个节点 nA；（对应函数
isSubStructure(A, B)）
2、
- 判断树 A 中 以 nA 为根节点的子树 是否包含树 B 。（对应函数
recur(A, B)）
recur(A, B) 函数：
终止条件：
当节点 BB 为空：说明树 BB 已匹配完成（越过叶子节点），因此返回 truetrue ；
当节点 AA 为空：说明已经越过树 AA 叶子节点，即匹配失败，返回 falsefalse ；
当节点 AA 和 BB 的值不同：说明匹配失败，返回 falsefalse ；
返回值：
判断 AA 和 BB 的左子节点是否相等，即 recur(A.left, B.left) ；
判断 AA 和 BB 的右子节点是否相等，即 recur(A.right, B.right) ；
isSubStructure(A, B) 函数：
特例处理： 当 树 AA 为空 或 树 BB 为空 时，直接返回 falsefalse ；
返回值： 若树 BB 是树 AA 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
以 节点 AA 为根节点的子树 包含树 BB ，对应 recur(A, B)；
树 BB 是 树 AA 左子树 的子结构，对应 isSubStructure(A.left, B)；
树 BB 是 树 AA 右子树 的子结构，对应 isSubStructure(A.right, B)；
以上 2. 3. 实质上是在对树 AA 做 先序遍历
最终是要让recur返回值为true才算找到（建议按照2部思路再带入实例一步一步判断）
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} A
* @param {TreeNode} B
* @return {boolean}
*/
/*
参考:数据结构与算法的题解比较好懂
死死记住isSubStructure()的定义:判断B是否为A的子结构
*/
var isSubStructure = function(A, B) {//先序遍历A中的每个结点，找B为A的子结构
if(A==null || B == null){
return false;
}
// B为A的子结构有3种情况,满足任意一种即可:
// 1.B的子结构起点为A的根节点,此时结果为recur(A,B)
// 2.B的子结构起点隐藏在A的左子树中,而不是直接为A的根节点,此时结果为isSubStructure(A.left, B)
// 3.B的子结构起点隐藏在A的右子树中,此时结果为isSubStructure(A.right, B)
return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};
var recur = function(A, B) {
// 若B走完了,说明查找完毕,B为A的子结构
if(B == null) {
return true;
}
// 若B不为空并且A为空或者A与B的值不相等,直接可以判断B不是A的子结构
if(A == null || A.val != B.val) {
return false;
}
// 当A与B当前节点值相等,若要判断B为A的子结构
// 还需要判断B的左子树是否为A左子树的子结构 && B的右子树是否为A右子树的子结构
// 若两者都满足就说明B是A的子结构,并且该子结构以A根节点为起点
return recur(A.left, B.left) && recur(A.right, B.right);
}