Java另一棵树的子树

这篇具有很好参考价值的文章主要介绍了Java另一棵树的子树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1.题目描述

2.题解

思路分析

具体实现

完整代码


1.题目描述

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例:

Java另一棵树的子树,Java刷题,算法,java,数据结构

输入:root = [3, 4, 5, 1, 2],subRoot = [4, 1, 2]

输出:true

2.题解

思路分析

我们首先判断两棵二叉树是否相同,若相同,则subRoot是root的子树;

若不相同,则判断root的左子树是否与subRoot是否相同,若相同,则subRoot是root的子树;

若不同,判断root的右子树是否与subRoot相同,若相同,subRoot是root的子树;

若不同,继续递归判断...

具体实现

1.首先实现判断两棵二叉树是否相同的代码:

(1)若两棵二叉树都为空,则两颗二叉树相同;若两颗二叉树中只有一棵树为空,则不同

(2)若两棵二叉树都不为空,再判断其根节点的值是否相同,若不相同,两棵二叉树不相同;若相同,再分别判断两颗二叉树的左子树是否相同,右子树是否相同。(通过递归实现)

具体过程:

Java另一棵树的子树,Java刷题,算法,java,数据结构

代码实现:

public boolean isSameTree(TreeNode p, TreeNode q) {
    //都为null,相同
    if(p == null && q == null){
        return true;
    }
    //只有一个为null,不同
    if(p == null||  q == null){
        return false;
    }
    //都不为空,但值不为空,不同
    if(p.val != q.val){
        return false;
    }
    //判断两颗二叉树的左子树、右子树是否相同
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}

2.判断subRoot是否为root子树

(1)若subRoot为空,则subRoot为root的子树,返回true

(2)若root为空,则subRoot不为root的子树。返回false

(1)判断subRoot是否与root相同

(2)判断subRoot是否是root的左子树

(3)判断subRoot是否是root的右子树

若都不相同,最后返回false

具体过程:

Java另一棵树的子树,Java刷题,算法,java,数据结构

代码实现:

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if(subRoot == null){
        return true;
    }
    if(root == null) {
        return false;
    }
    //1、是不是和根节点相同
    if(isSameTree(root,subRoot)) {
        return true;
    }
    //2、判断是不是root的左子树
    if(isSubtree(root.left,subRoot)) {
        return true;
    }
    //3、右子树
    if(isSubtree(root.right,subRoot)) {
        return true;
    }
    //4、返回
    return false;
}

完整代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if(p == null && q == null){
            return true;
        }
        if(p == null||  q == null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot == null){
            return true;
        }
        if(root == null) {
            return false;
        }
        //1、是不是和根节点相同
        if(isSameTree(root,subRoot)) {
            return true;
        }
        //2、判断是不是root的左子树
        if(isSubtree(root.left,subRoot)) {
            return true;
        }
        //3、右子树
        if(isSubtree(root.right,subRoot)) {
            return true;
        }
        //4、返回
        return false;
    }
}

题目来自:

572. 另一棵树的子树 - 力扣(LeetCode)文章来源地址https://www.toymoban.com/news/detail-715440.html

到了这里,关于Java另一棵树的子树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 手撕数据结构与算法——树(三指针描述一棵树)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:king南星 📖

    2024年01月17日
    浏览(58)
  • 数据结构中的一棵树

    一、树是什么? 有根有枝叶便是树!根只有一个,枝叶可以有,也可以没有,可以有一个,也可以有很多。 就像这样: 嗯,应该是这样: 二、一些概念 1、高度 树有多高,嗯,我一米八三! 树的高度怎么算? 高度是啥,就是从下往上到最顶端,从叶节点到根节点。 从每个

    2024年01月21日
    浏览(35)
  • 根据列表构造一棵树

    List allMenus = menuDao.findBy(“status”, Status.AVAILABLE.getKey(), “priority”, false); List rootMenu = new ArrayList (); if (CollectionUtils.isNotEmpty(allMenus)) { MapLong, Menu menuMap = new HashMapLong, Menu(); for (Menu menu : allMenus) { if (menu.getParentId() == null) { rootMenu.add(menu); } menuMap.put(menu.getId(), menu); } for (Menu menu :

    2024年02月08日
    浏览(33)
  • 【数据结构】用Java实现一棵二叉树

    目录 前言 1. 创建MyBinaryTree类 2. 从前序与中序遍历序列构造二叉树 3. 从中序与后序遍历序列构造二叉树 4. 用层序遍历验证二叉树是否构建成功 5. 整体代码(构建二叉树、二叉树的基本功能和测试代码) 6. 测试结果 前面两篇文章已经给出了如何构建二叉树以及如何实现基本

    2024年02月11日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(46)
  • java数据结构与算法刷题-----LeetCode287. 寻找重复数

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤 判断是否有环,并得到快慢指针相遇

    2024年01月24日
    浏览(43)
  • java数据结构与算法刷题-----LeetCode766. 托普利茨矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 这道题只要换一种理解方式,瞬间就会变的很简单。 题目描述是每个元素左上和右下对角线元素都相同。但是,我们发

    2024年01月25日
    浏览(48)
  • java数据结构与算法刷题-----LeetCode667. 优美的排列 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组,必须含有1~n的所有数,并且从左到右,相邻的元素依次相减,它们的差,必

    2024年01月25日
    浏览(52)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包