首页 > 试题广场 >

树的子结构

[编程题]树的子结构
  • 热度指数：953703 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
示例1

输入

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

输出

true
示例2

输入

{1,2,3,4,5},{2,4}

输出

true
示例3

输入

{1,2,3},{3,1}

输出

false

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Javascript
牛客246205877号头像 牛客246205877号 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(pRoot1, pRoot2)
{
    if(!pRoot1 || !pRoot2) return false;
    let result = false
    if(pRoot1.val === pRoot2.val){
       result = isSameSubtree(pRoot1, pRoot2)
    }
    if(!result && pRoot1.left){
        result = HasSubtree(pRoot1.left, pRoot2)
    }
    if(!result && pRoot1.right){
        result = HasSubtree(pRoot1.right, pRoot2)
    }
    return result
}

function isSameSubtree(pRoot1, pRoot2){
    if(!pRoot1 && pRoot2) return false;
    if(!pRoot2) return true
    const { left:left1, right:right1,val:val1 } = pRoot1;
    const { left:left2, right:right2, val:val2 } = pRoot2;
    let result = false;
    if(val1 === val2){
        result = isSameSubtree(left1, left2) && isSameSubtree(right1, right2) 
    }
    return result
}


module.exports = {
    HasSubtree : HasSubtree
};

发表于 2021-09-08 15:37:05 回复(0)
JavaScript
别卷啦！头像 别卷啦！
比较B是不是A的子树，B是不是A的右子树的子树，B是不是A的左子树的子树。如果根元素相同，则开始判断左子树和右子树 
function HasSubtree(A, B)
{
    // write code here
    if(!A||!B){
    return false
}
return isSameTree(A, B) || HasSubtree(A.left, B) || HasSubtree(A.right, B)
};
var isSameTree = function(A, B){
    if(!B) return true
    if(!A) return false
    if(A.val !== B.val) return false
    return isSameTree(A.left, B.left) && isSameTree(A.right, B.right)
}

发表于 2021-07-04 21:41:52 回复(0)
JavaScript
牛客-skinner头像 牛客-skinner
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    if(!pRoot1 || !pRoot2){
        return false
    }
    
    if(!compTree(pRoot1,pRoot2)){
        return HasSubtree(pRoot1.left,pRoot2) || HasSubtree(pRoot1.right,pRoot2)
    }
    return true
    
    
    
    
    //比较两棵树是否相同
    function compTree(root1,root2){
        if(!root2){
            return true
        }
        if(!root1){
            return false
        }
        if(root1.val !== root2.val){
            return false
        }
        return compTree(root1.left,root2.left) && compTree(root1.right,root2.right)
    }
}
module.exports = {
    HasSubtree : HasSubtree
};
发表于 2021-03-28 12:05:00 回复(0)
JavaScript
牛客836708999号头像 牛客836708999号
js V8 的用例是不是有问题？我用node输同样的代码就能通过。。
发表于 2021-03-14 19:21:12 回复(0)
JavaScript
木人R头像 木人R
比较两个树的先序遍历结果不就行了？
发表于 2020-11-12 12:50:55 回复(0)
JavaScript
许愿2020offer头像 许愿2020offer 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
//注意子结构，和子树并不一致，子树的判断：我的想法是先通过b的中序遍历得到数组，
//再去判断a的根节点是不是在b的数组中，再去判断左右节点是不是也一样，子树的意思是包含了
//一个结点，就得包含这个结点下的所有节点，一棵大小为n的二叉树有n个子树，就是分别以每个结点
//为根的子树。子结构的意思是包含了一个结点，可以只取左子树或者右子树，或者都不取。
//子树的判断要比子结构复杂
function HasSubtree(pRoot1, pRoot2)
{
    if（!pRoot1 || !pRoot2） return false
    return isSubTree(pRoot1,pRoot2)||HasSubtree(pRoot1.left,pRoot2)||HasSubtree(pRoot1.right,pRoot2)
    function isSubTree(p,q){
        if(!q) return true
        if(!p) return false
        if(p.val===q.val){
            return isSubTree(p.left,p.left)&&isSubTree(p.right,p.right)
        }
        else 
            return false
    }
}// write code here

发表于 2020-08-14 13:29:34 回复(0)
JavaScript
牛客75263145头像 牛客75263145
//比较node1是否包含node2
const compare = function(node1, node2) {
    if(node2 == null) return true //node2为空node1可以为任何值
    if(node1 == null) return false //此时node2 肯定不为空 , node1却为空, 不满足条件
    if(node1.val !== node2.val) return false //节点值不相等直接return false
    return compare(node1.left, node2.left) && compare(node1.right, node2.right) //再比较左右节点
}
function HasSubtree(root1, root2)
{    
    if(root2 == null || root1 == null) return false
    if(root1.val === root2.val && compare(root1, root2)) return true
    return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2)
}
发表于 2020-05-10 20:03:45 回复(0)
JavaScript
Amber_gzl头像 Amber_gzl 
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    if(pRoot2 == null || pRoot1 == null) return false;
    if(pRoot1.val == pRoot2.val){
        if(IsEqual(pRoot1, pRoot2) == true) return true;
    }
    return HasSubtree(pRoot1.left, pRoot2)||HasSubtree(pRoot1.right, pRoot2);
    
}
function IsEqual(pRoot1, pRoot2){
    if(pRoot2 == null) return true;
    if(pRoot1 == null && pRoot2 !=null) return false;
    if(pRoot1.val != pRoot2.val) return false;
    else if(pRoot1.val == pRoot2.val)
        return IsEqual(pRoot1.left, pRoot2.left)&&IsEqual(pRoot1.right, pRoot2.right);
}

发表于 2020-03-13 19:19:58 回复(0)
JavaScript
Helianthuswhite头像 Helianthuswhite 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

/**
 * 我的解题思路：
 * 1.思路是比较简单的，从父树的根节点开始，依次与子树进行节点比较
 * 2.当找到相同节点时，同时递归比较左节点和右节点是否相同
 * 4.这里有几个需要注意的点：
 *   - 递归比较时的终止条件为父树节点不存在或者子树节点不存在，且两种情况返回值不同
 *   - 递归终止时，需要先判断子树节点，再判断父树节点
 *   - 对父树根节点比较时，需要用额外空间存储每次比较的结果，用于判断下次是否需要进行比较
 *
 * @param {*} pRoot1 
 * @param {*} pRoot2 
 */
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    if (!pRoot1 || !pRoot2) {
        return false;
    }

    const func = (p1, p2) => {
        if (!p2) {
            return true;
        }
        if (!p1) {
            return false;
        }
        if (p1.val === p2.val) {
            return func(p1.left, p2.left) && func(p1.right,p2.right);
        }
        return false;
    };

    let result = false;
    if (pRoot1.val === pRoot2.val) {
        result = func(pRoot1, pRoot2);
    }
    if (!result) {
        result = func(pRoot1.left, pRoot2);
    }
    if (!result) {
        result = func(pRoot1.right, pRoot2);
    }
    return result;
}

/**
 * 评论区TOP的解题思路：
 * 思路跟我的思路一致，不过有一些优化的写法
 *
 * @param {*} pRoot1 
 * @param {*} pRoot2 
 */
function topHasSubtree(pRoot1, pRoot2) {
    // write code here
    if (!pRoot1 || !pRoot2) {
        return false;
    }

    const func = (p1, p2) => {
        if (!p2) {
            return true;
        }
        if (!p1) {
            return false;
        }
        return p1.val === p2.val ? func(p1.left, p2.left) && func(p1.right,p2.right) : false;
    };

    return func(pRoot1, pRoot2) || func(pRoot1.left, pRoot2) || func(pRoot1.right, pRoot2);
}

发表于 2020-03-01 16:36:24 回复(0)
JavaScript
dellyoung头像 dellyoung
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
/*
一、HasSubtree 找A节点中和B节点值相同的节点
设置变量resp compare的值
1、当A或者B任何一个为null时，返回false
2、当A.val===B.val时，调用compare
3、resp为false 递归遍历左子树
4、resp还为false 递归遍历右子树
5、返回resp

二、compare 比较a b节点是否完全相同
逆向思维 递归遍历
当b节点不为null时，遍历没有结束
a节点为null，返回false
A.val!==B.val，返回false

当b节点为null时，遍历结束，
返回true

递归遍历，当左右子树都返回true则a，b节点相等
*/
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    let resp = false;
    if(!(pRoot1 && pRoot2)){
        return false;
    }
    if(pRoot1.val === pRoot2.val){
        resp = compare(pRoot1,pRoot2)
    }
    if(!resp){
        resp = HasSubtree(pRoot1.left,pRoot2)
    }
    if(!resp){
        resp = HasSubtree(pRoot1.right,pRoot2)
    }
    return resp;
}

function compare(pRoot1, pRoot2){
    if(pRoot2 === null){
        return true
    }
    if(pRoot1 === null){
        return false
    }
    if(pRoot1.val !== pRoot2.val){
        return false
    }
    return compare(pRoot1.left, pRoot2.left) && compare(pRoot1.right, pRoot2.right)
}


发表于 2020-02-08 11:19:05 回复(0)
JavaScript
Bytedancer2021头像 Bytedancer2021 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    if(!pRoot1 || !pRoot2) return false;
    if(compare(pRoot1, pRoot2)){
        return true;
    }else{
        let status = false;
        if(pRoot1.left){
            status = status || HasSubtree(pRoot1.left, pRoot2);
        }
        if(pRoot1.right){
            status = status || HasSubtree(pRoot1.right, pRoot2);
        }
        return status;
    }
}
function compare(root1, root2){
    if(!root2) return true;
    if(!root1 || root1.val !== root2.val){
        return false;
    }else{
        return compare(root1.left, root2.left) && compare(root1.right, root2.right)
    }
}

发表于 2019-09-16 19:21:01 回复(0)
JavaScript
不去大厂不换昵称头像 不去大厂不换昵称
1.在A树中找到和B树值一样的节点R
2.判断A中以R为跟节点的子树是否包含B树这样的子结构
递归二叉树找到值相同的节点
递归该节点左右子树判断是否包含 

    function HasSubtree(pRoot1, pRoot2) {
      let result = false;
      if (pRoot1 && pRoot2) {
        if (pRoot1.val === pRoot2.val) {
          result = compare(pRoot1, pRoot2);
        }
        if (!result) {
          result = HasSubtree(pRoot1.right, pRoot2);
        }
        if (!result) {
          result = HasSubtree(pRoot1.left, pRoot2);
        }
      }
      return result;
    }

    function compare(pRoot1, pRoot2) {
      if (pRoot2 === null) {
        return true;
      }
      if (pRoot1 === null) {
        return false;
      }
      if (pRoot1.val !== pRoot2.val) {
        return false;
      }
      return compare(pRoot1.right, pRoot2.right) && compare(pRoot1.left, pRoot2.left);
    }

发表于 2019-01-31 14:29:30 回复(0)
JavaScript
79606710头像 79606710
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(pRoot1, pRoot2)
{
    var res=false;
    if(pRoot1!==null&&pRoot2!==null){
        if(pRoot1.val===pRoot2.val){
            res=judge(pRoot1,pRoot2);
        }
        if(!res){
            res=HasSubtree(pRoot1.left,pRoot2);
        }
        if(!res){
            res=HasSubtree(pRoot1.right,pRoot2);
        }
    }
    return res;
}

function judge(r1,r2){
    if(r2===null){
        return true;
    }
    if(r1===null){
        return false;
    }
    if(r1.val!==r2.val){
        return false;
    }
    return judge(r1.left,r2.left)&&judge(r1.right,r2.right);
}
发表于 2019-01-16 21:52:15 回复(1)
JavaScript
码数不够头像 码数不够 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
/*先序遍历*/
function preOrder(tmp,arr){
    arr.push(tmp.val);
    if(tmp.left != null)
        preOrder(tmp.left,arr);
    if(tmp.right != null)
        preOrder(tmp.right,arr);
}
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    if(pRoot2 == null)
        return false;
    if(pRoot1 == null && pRoot2 != null)
        return false;
    var arrc = [],
        arrf = [];
    preOrder(pRoot1,arrf);
    preOrder(pRoot2,arrc);
    if(arrf.join().includes(arrc.join()))
        return true
    else
        return false;
}
发表于 2018-10-12 00:01:35 回复(0)
JavaScript
是函数不是方法头像 是函数不是方法
和leetcode稍微不同。比如[8,8,7,9,2,null,null,null,null,4,7]，[8,9,2]在leetcode中是false，在剑指里是true。看了一下发现不需要子树完全相同，只要有这个结构即可，感觉这个就是坑之所在吧。主要思路是构建一个sameTree来判断以当前节点为root的树是不是符合条件。如果pRoot2还没有遍历到叶而pRoot1已经到了，此时才返回false。然后循环遍历左右子树。 
function sameTree(pRoot1, pRoot2){
    if(pRoot2 === null){
        return true;
    }
    if(pRoot1 === null && pRoot2 !== null){
        return false;
    }
    return pRoot1.val === pRoot2.val && sameTree(pRoot1.left, pRoot2.left) && sameTree(pRoot1.right, pRoot2.right);
}
function HasSubtree(pRoot1, pRoot2)
{
    if(pRoot1 === null || pRoot2 === null){
        return false;
    }
    if(sameTree(pRoot1, pRoot2)){
        return true;
    }
    return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
}

发表于 2018-08-07 12:20:34 回复(0)
JavaScript
求一个offer啊啊啊头像 求一个offer啊啊啊 
function isSubtree(pRoot1, pRoot2) {
      if (!pRoot2) return true;
      if (!pRoot1) return false;
      if (pRoot1.val != pRoot2.val) {
        return false;
      } else {
        return isSubtree(pRoot1.left, pRoot2.left) && isSubtree(pRoot1.right, pRoot2.right);
      }
    }

    function HasSubtree(pRoot1, pRoot2) {
      // write code here
      if (pRoot2 == null || pRoot1 == null) return false;
      return isSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
    }

发表于 2018-06-02 10:49:12 回复(0)
JavaScript
触底翻盘头像 触底翻盘
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    var result = false;
    if(pRoot1 === null||pRoot2 === null){
        return false;
    }else{
        if(pRoot1.val === pRoot2.val){
            result = DoesTree1HasTree2(pRoot1, pRoot2);
        }
        if(!result){
            result = HasSubtree(pRoot1.left,pRoot2)
        }
        if(!result){
            result = HasSubtree(pRoot1.right,pRoot2)
        }
    }
    return result;
}
function DoesTree1HasTree2(pRoot1, pRoot2){
    if(pRoot2 === null){
        return true;
    }
    if(pRoot1 === null){
        return false;
    }
    if(pRoot1.val === pRoot2.val){
        return DoesTree1HasTree2(pRoot1.left, pRoot2.left) && DoesTree1HasTree2(pRoot1.right, pRoot2.right)
    }
    return false;
}

发表于 2018-05-09 11:11:19 回复(0)
JavaScript
子尧头像 子尧 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    if(pRoot1 == null || pRoot2 == null){
        return false;
    }
    if(pRoot1.val == pRoot2.val && pRoot2.right == null && pRoot2.left == null){
        return true;
    }
    if(pRoot1.val == pRoot2.val){
        if(!pRoot1.left && !pRoot2.left){
            return HasSubtree(pRoot1.right, pRoot2.right);
        }
        if(!pRoot1.right && !pRoot2.right){
            return HasSubtree(pRoot1.left, pRoot2.left);
        }
        if(HasSubtree(pRoot1.left, pRoot2.left) && HasSubtree(pRoot1.right, pRoot2.right)){
           return true;
        }
    }
    return (HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2))
}

发表于 2018-04-07 17:37:01 回复(0)
JavaScript
Zfirsty头像 Zfirsty 
//Javascript 描述，用flag表示函数状态。
function HasSubtree(p1, p2,flag)
{
    var f=HasSubtree;
    if(flag && !p2) return true;
    if(!p1 || !p2) return false;
    if(p1 && p2 && p1.val == p2.val) 
        return f(p1.left,p2.left,true) && f(p1.right,p2.right,true) || f(p1.left,p2)||f(p1.right,p2);
    return  f(p1.left,p2) || f(p1.right,p2);
}

编辑于 2017-09-19 22:15:03 回复(0)
提交观点

问题信息

树 二叉树
难度：
20条回答 175071浏览

热门推荐

通过挑战的用户

查看代码

相关试题

树的子结构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号