第26题 – 树的子结构

作者: 周伟林 分类: 剑指offer 发布时间: 2018-05-19 21:49

牛客链接

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

解题思路

递归调用。第一个函数负责递归、第二个函数判断两棵树相同位置的元素是否相同。

JavaScript实现

function HasSubtree(pRoot1, pRoot2)
{
    if(!pRoot1 || !pRoot2) return false;
    return isSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
}
function isSubtree(pRoot1, pRoot2) {
    if(pRoot2 === null) return true;
    if(pRoot1 === null) return false;
    if(Math.abs(pRoot1.val - pRoot2.val) < 1e-7){
        return isSubtree(pRoot1.left, pRoot2.left) && isSubtree(pRoot1.right, pRoot2.right);
    }else{
        return false;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注