树的子结构

题目

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

创建树代码

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
var root1=new TreeNode(1)
var a=new TreeNode(2)
var b=new TreeNode(3)
var c=new TreeNode(4)
var d=new TreeNode(5)
var e=new TreeNode(6)
root1.left=a;
root1.right=b;
a.left=c;
a.right=d;
b.left=e;

var root2=new TreeNode(2)
var f=new TreeNode(4)
var g=new TreeNode(6)
root2.left=f;
root2.right=g;

console.log(HasSubtree1(root1,root2))//测试

方法一：

思路：队列存储A树，当A中shift()取得的树的val值等于B根的值时，进行子树判定，为子树则直接return,否则继续执行，直至队列为空。

代码

function HasSubtree(pRoot1, pRoot2)
{
    if(pRoot2==null||pRoot1==null)
        return false;
    var array=[];
    var item;
    array.push(pRoot1);
    while(array.length!=0){
        item=array.shift();//取最前面的一个

        if(item.val==pRoot2.val){
            var res=Judge(item,pRoot2)
            if(res){
                return true;
            }
        }
        if(item.left!=null){
            array.push(item.left)
        }
        if(item.right!=null){
            array.push(item.right)
        }

    }
    return false;
}

function Judge(p,q){
    // console.log(p,q)
    if(p.val==q.val){
        if(q.left==null&&q.right==null){  //叶子结点
            return true;
        }
        if((p.left==null&&q.left!=null)||(p.right==null&&q.right!=null)){
            return false;
        }
        var left=true,right=true;
        if(p.left!=null&&q.left!=null){
            left=Judge(p.left,q.left);
            // console.log("left**--",left)
        }
        if(p.right!=null&&q.right!=null){
            right=Judge(p.right,q.right);
            // console.log("right**--",right)
        }
        // console.log("back**--",left&&right)
        return left&&right;
    }
    return false;
}

方法二

思路：不在需要队列，每次在当前A根时判断是否匹配时，同时递归调用去判断它的左右子树匹配情况。一旦匹配则结束

代码

function isSubtree(pRoot1, pRoot2){
    if(pRoot2==null)
        return true;
    if(pRoot1==null)//此时pRoot2必定不为null
        return false;
    if(pRoot2.val==pRoot1.val){
        return isSubtree(pRoot1.left,pRoot2.left)&&isSubtree(pRoot1.right,pRoot2.right)
    }
    return false;
}
function HasSubtree(pRoot1, pRoot2){
    if(pRoot1==null||pRoot2==null){
        return false;
    }
    return isSubtree(pRoot1, pRoot2)||HasSubtree(pRoot1.left,pRoot2)||HasSubtree(pRoot1.right,pRoot2)
}

根据提交结果，方法二稍快一点。