树的子结构

《剑指offer》刷题笔记。如有更好解法，欢迎留言。

关键字：二叉树 递归

题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：

• 双递归：第一层递归判断二叉树A是否存在节点等于二叉树B的根。
• 如果存在这样一个节点，那么对比A的子树与二叉树B。
• 结束条件：当二叉树B全部节点被遍历完，A的子树还没遍历完，说明B是A的一部分，返回true，否则为false。
• 完整代码

function compare(root1,root2){
    if(root2 === null) return true;
    if(root1 === null) return false;
    if(root1.val === root2.val){
        return compare(root1.left,root2.left)&&compare(root1.right,root2.right);
    }else{
        return false;
    }
}
function HasSubtree(pRoot1, pRoot2)
{
    if(pRoot1 === null || pRoot2 === null) return false;
    return compare(pRoot1,pRoot2) 
    ||  HasSubtree(pRoot1.left,pRoot2) || HasSubtree(pRoot1.right,pRoot2);
}