前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >牛客网-树的子结构

牛客网-树的子结构

作者头像
手撕代码八百里
发布2020-07-28 17:30:36
3190
发布2020-07-28 17:30:36
举报
文章被收录于专栏:猿计划猿计划

题目描述

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

oj连接: https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88

解法1

代码语言:javascript
复制
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    
    public boolean is(TreeNode root1,TreeNode root2){
            //root2等于null时,说明已经比较完了,就返回true
            if(root2 ==null)
                return true;
            //root1等于null时,说明root2不是root1的子树,返回false
            if(root1 ==null)
                return false;
            //如果root1和root2的值不一样,就返回false
            if(root1.val != root2.val)
                return false;
            //如果一样,就继续比较root1和root2的左节点和右节点。
            return is(root1.left,root2.left) && is(root1.right,root2.right);
    }
    
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //如果有一个为null,就直接返回false,因为空的树,不是任何一个树的子树
        if(root1 == null || root2 ==null)
            return false;
        
        boolean bool = false;
        
        //找到相等的一个,从相等的根节点处开始比较左右子节点
        if(root1.val == root2.val){
            bool = is(root1,root2);
        }
        
        //如果root1,val != root2.val 那么就继续寻找左右子节点
        if(bool != true)
            bool = HasSubtree(root1.left,root2);
        //如果还等于false,说明在left中没有找到,就继续找right
        if(bool != true)
            bool = HasSubtree(root1.right,root2);
        
        return bool;
        
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-07-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 解法1
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档