题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
示例1
输入
{8,8,#,9,#,2,#,5},{8,9,#,2}
返回值
true
思路：
１． 设计match函数来匹配在ａ树中是否含有ｂ树（此时ａ和ｂ的ｖａｌｕｅ值相等）；
２． 遍历整个大树，找到与root2的值相等的节点，并使用ｍａｔｃｈ函数。
match函数分析：
很明显要使用递归。
递归的基本功能：
如果在ａ树中发现一个节点的值不等于ｂ树中对应位置的值，则返回ｆａｌｓｅ：
if(a.val != b.val){
return false;
}
递归终止条件：
（１） 如果b树已经遍历完，还没有返回ｆａｌｓｅ，那么说明b确实是ａ的子结构；
（２） 如果在ｂ树没有遍历完毕的基础上，a树已经遍历完毕，那么说明ｂ并不是ａ的子结构。
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 ==null){
return false;
}
return match(root1,root2) || HasSubtree(root1.left,root2)|| HasSubtree(root1.right,root2);
}
boolean match(TreeNode a, TreeNode b){
if(b == null){
return true;
}
if(a == null){
return false;
}
if(a.val != b.val){
return false;
}
return (match(a.left,b.left) && match(a.right,b.right));
}
}
