题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
function HasSubtree(pRoot1, pRoot2)
{
// 两树任意一个为空或都为空,返回false
if(pRoot2==null || pRoot1==null){
return false
}
//判断树2跟树1结构、树2跟树1左子树结构、树2跟树1右子树结构,有一个返回true,则树2是树1的子结构
return doesTree1HasTree2(pRoot1,pRoot2) || doesTree1HasTree2(pRoot1.left,pRoot2) || doesTree1HasTree2(pRoot1.right,pRoot2)
}
function doesTree1HasTree2(tree1, tree2){
//终止条件
if(tree2==null){
return true
}
if(tree1==null){
return false
}
if(tree1.val!==tree2.val){
return false
}
//递归判断双方每个节点是否一样,直至一方为空,终止跳出程序
return doesTree1HasTree2(tree1.left,tree2.left) && doesTree1HasTree2(tree1.right,tree2.right)
}