剑指 Offer 26. 树的子结构（中等）

通过率 46.4%

题目链接

题目描述：

输入两棵二叉树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

思路：

这题没有明确的思路，然后看了Krahets大神的题解

不能清楚地说出自己的理解的话，那这种逻辑思维就无法吸收为自己的，现在，要用我自己的话理一理思路（貌似没有大神的好懂...不过自己看看就好(#^.^#)）：

遍历A树的每个节点，判断以该节点为根节点的树是否包含B树（即调用函数isSubStructure）
若该节点的val值等于B的根节点的val值，则递归判断以该节点为根节点的树是否能与B树匹配（调用函数sub）

也就是说，每遍历一个节点，都调用isSubStructure(node.left/right, B)；一旦遇到node.val === B.val的情况，就先调用sub(node, B)，真正能判断A树中是否包含B树的其实是sub()函数

 1 /*JavaScript*/
 2 /**
 3  * Definition for a binary tree node.
 4  * function TreeNode(val) {
 5  *     this.val = val;
 6  *     this.left = this.right = null;
 7  * }
 8  */
 9 /**
10  * @param {TreeNode} A
11  * @param {TreeNode} B
12  * @return {boolean}
13  */
14 var sub = function(x, y) {
15     if(!y) return true //B树已走到叶子节点，说明x包含y
16     if(!x || x.val !== y.val) return false //B未走到叶子节点而A已走到叶子节点 或者 值不等
17     return sub(x.left, y.left) && sub(x.right, y.right) //值相等，则判断左右子树是否能匹配
18 }
19 
20 var isSubStructure = function(A, B) {
21     if(!A || !B) return false //A或B为空树
22     return A.val === B.val && sub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
23 };