网络异常，图片无法展示
|
输入两棵二叉树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 的子树
要判断 B 是否是 A 的子结构，可以通过 B 与 A 及 A 的每一个子树对比的结果判断
如果找到 A 的某个子树和 B 匹配，返回 true 如果遍历完所有子树都没有和 B 匹配的子树，返回 false
动画演示如下：
网络异常，图片无法展示
|
代码如下：
var isSubStructure = function(A, B) { // 特判空树不是任意一个树的子结构 if(B===null) return false; // 对比root2是否是root1的子树 function compare(root1,root2){ if((root1===null&&root2===null)||(root1&&root2===null)) return true; if((root1===null&&root2)||(root1.val!==root2.val)) return false; return compare(root1.left,root2.left)&&compare(root1.right,root2.right) } // 递归获取二叉树的子树 function traverse(root){ if(root === null) return false; if(compare(root,B)) return true; return traverse(root.left) || traverse(root.right); } // 返回结果 return traverse(A); }; 复制代码
至此我们就完成了 leetcode-剑指 Offer 26-树的子结构
如有任何问题或建议，欢迎留言讨论！
