二叉树相关习题

题目:100. 相同的树 - 力扣(LeetCode)

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入:p = [1,2,3], q = [1,2,3]
输出:true

示例 2:

输入:p = [1,2], q = [1,null,2]
输出:false

示例 3:

输入:p = [1,2,1], q = [1,1,2]
输出:false

提示:

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

思路:1.先判断一个为空一个不为空的情况

    2.在判断两个都为空的情况

    3.都不为空时,判断值是否相等

    4.递归左右子树。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //一个为空一个不为空
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        //两个都为空
        if(p==null&&q==null){
            return true;
        }
        //走到这里这时两个都不为空了,判断值是否相等
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left ,q.left)&&
        isSameTree(p.right ,q.right);
        
    }
}

 题目:572. 另一棵树的子树 - 力扣(LeetCode)

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

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

示例 1:

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

示例 2:

输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出:false

提示:

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

思路:1.先判空,空也是false因为空也算一个节点,不确定后面有没有

2.在判断两树是否相同

3.递归判断左右子树是否相同

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //一个为空一个不为空
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        //两个都为空
        if(p==null&&q==null){
            return true;
        }
        //走到这里这时两个都不为空了,判断值是否相等
        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(root==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
}

题目:226. 翻转二叉树 - 力扣(LeetCode)
 

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

示例 1:

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

示例 2:

输入:root = [2,1,3]
输出:[2,3,1]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

思路:1.判空

    2.交换左右子树的结点

    3.递归左右子树

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

题目:110. 平衡二叉树 - 力扣(LeetCode)

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

示例 3:

输入:root = []
输出:true

提示:

  • 树中的节点数在范围 [0, 5000]
  • -104 <= Node.val <= 104

思路:平衡二叉树指的是子树之间的绝对值之差小于1。

用两个方法写(高度,平衡)

高度1.判空

2.递归左右子树的高度并保存

3.判断绝对值之差是否小于1,并且递归的左右子树都要>=0

返回最大子树的高度+1.

平衡:1.判空,空也平衡

2.返回高度>0.

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int getHeight(TreeNode root){
        if(root==null)return 0;
        int leftHeight=getHeight(root.left);
        int righeHeight=getHeight(root.right);
        if(leftHeight>=0&&righeHeight>=0&&
        Math.abs(leftHeight-righeHeight)<=1){
            return Math.max(leftHeight,righeHeight)+1;
        }else{
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return getHeight(root)>0;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/910543.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

阅读笔记记录

论文作者将对话建模成一个seq2seq的映射问题&#xff0c;该seq2seq框架以对话历史数据&#xff08;通过belief tracker建模&#xff09;和数据库查询结果&#xff08;通过Database Operator得到结果&#xff09;作为支撑。 Abstract 教会机器完成与人自然交流的任务是充满挑战…

测试分层:减少对全链路回归依赖的探索!

引言&#xff1a;测试分层与全链路回归的挑战 在软件开发和测试过程中&#xff0c;全链路回归测试往往是一个复杂且耗费资源的环节&#xff0c;尤其在系统庞大且模块众多的场景下&#xff0c;全链路测试的集成难度显著提高。而“测试分层”作为一种结构化的测试方法&#xff0…

融合虚拟化与容器技术,打造灵活又安全的AI算力服务

随着人工智能技术的不断进步&#xff0c;AI企业在迅速推进大模型业务时&#xff0c;往往会倾向于采用容器化的轻量部署方案。相较于传统的虚拟机部署&#xff0c;容器化在快速部署、资源利用、环境一致性和自动化编排等方面具备显著优势。 然而&#xff0c;容器技术所固有的隔…

协程3 --- golang的协程调度

文章目录 单进程时代多进程/线程时代协程时代内核级线程模型&#xff08;1&#xff1a;1&#xff09;用户级线程模型&#xff08;N&#xff1a;1&#xff09;两级线程模型CMP&#xff08;M&#xff1a;N&#xff09;GM模型 GMP模型 单进程时代 描述&#xff1a;每一个程序就是一…

微服务透传日志traceId

问题 在微服务架构中&#xff0c;一次业务执行完可能需要跨多个服务&#xff0c;这个时候&#xff0c;我们想看到业务完整的日志信息&#xff0c;就要从各个服务中获取&#xff0c;即便是使用了ELK把日志收集到一起&#xff0c;但如果不做处理&#xff0c;也是无法完整把一次业…

【原创】java+ssm+mysql收纳培训网系统设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…

apache poi 实现下拉框联动校验

apache poi 提供了 DataValidation​ 接口 让我们可以轻松实现 Excel 下拉框数据局校验。但是下拉框联动校验是无法直接通过 DataValidation ​实现&#xff0c;所以我们可以通过其他方式间接实现。 ‍ 步骤如下&#xff1a; 创建一个隐藏 sheet private static void create…

Linux权限概念 | 权限修改

文章目录 1.Linux的权限概念2.Linux权限管理3.文件访问权限的相关设置方法 1.Linux的权限概念 Linux下有两种用户&#xff1a;超级用户&#xff08;root&#xff09;和普通用户。对应root用户而言&#xff1a;可以在Linux系统下做任何事情&#xff0c;不受限制。而普通用户&am…

题目练习之二叉树那些事儿(续集)

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥ ♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥ ♥♥♥我们一起努力成为更好的自己~♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥ 这一篇博客我们继…

删除MacOS下PowerPoint烦人的加载项

起因 最近要写论文&#xff0c;需要插入很多公式&#xff0c;利用自带的吧&#xff0c;太过繁琐&#xff0c;每次插入都需要点击插入-公式-符号&#xff0c;然后头脑发热想用下本科写论文时用过的MathType&#xff0c;结果这货现在要收费了&#xff0c;新版本只能适用30天&…

清华双臂机器人扩散大模型RDT:先预训练后微调,支持语言、图像、动作多种输入(1B参数)

前言 通过上文介绍的GR2&#xff0c;我们看到了视频生成模型在机器人训练中的应用 无独有偶&#xff0c;和GR2差不多一个时期出来的清华RDT&#xff0c;其模型架构便基于视频生成架构DiT改造而成(当然&#xff0c;该清华团队其实也在DiT之前推出了U-ViT&#xff0c;具体下文会…

Linux下GCC编译器的安装

Linux下GCC编译器的安装 以下所有的版本都可以在https://gcc.gnu.org/pub/gcc/infrastructure/这里找最新的 通过apt-get方式下载的Qt5.9的gcc编译器版本只是4.8.3&#xff0c;无法打开一些Qt5的库头文件&#xff0c;所以准备在Llinux下再安装一个gcc5.3.0。 查看gcc版本 ubu…

qt相关知识

lineEdit中的一些知识 首先我要设置lineEdit中的文本怎么操作 ui->lineEdit->setText(); 如何给窗口设置名字 this->setWindowTitle("计算器"); 如何给按钮设置我们的图片 QIcon ic("图片地址")&#xff1b; ui->button->setIcon(ic…

使用官网tar包制作OpenSSL及OpenSSH rpm包进行升级安装(OpenSSH_9.9p1, without OpenSSL未解决)

一、制作openssl-1.1.1w.rpm包 1、安装基础依赖包和rpmbuild及其依赖包 yum install curl which make gcc perl perl-WWW-Curl rpm-build rpm-build rpmdevtools tree -y yum install gcc-c glibc glibc-devel openssl openssl-devel \pcre-devel zlib zlib-devel perl…

WAL日志

1.WAL概述 PG WAL&#xff08;Write-Ahead Logging&#xff09;日志是PostgreSQL数据库中的一种重要机制&#xff0c;用于保证数据库的完整性和数据恢复。 1.1定义与功能 WAL日志是PostgreSQL的持久性技术&#xff0c;它将所有对数据库的修改操作&#xff08;如INSERT、UPDA…

开放寻址法、链式哈希数据结构详细解读

一、开放寻址法&#xff08;Open Addressing&#xff09; 1. 定义 开放寻址法是一种哈希冲突解决策略&#xff0c;所有元素都存储在哈希表中。当发生冲突时&#xff0c;即两个键计算出的哈希值相同时&#xff0c;会按照一定的探查序列查找下一个可用的位置来存储新元素。 2.…

算法通关(4)-- 前缀树

前缀数原理和代码 原理 前缀树&#xff08;Trie树&#xff09;&#xff0c;也称为字典树&#xff0c;是一种用于高效存储和检索字符串的数据结构。它是一种树形结构&#xff0c;能够利用字符串的公共前缀来减少存储空间和查询时间。 现在有“acb”,"cba","ac…

CSS3新增渐变(线性渐变、径向渐变、重复渐变)

1.线性渐变 代码&#xff1a; 效果图&#xff1a; 使文字填充背景颜色&#xff1a; 效果图&#xff1a; 2.径向渐变 代码&#xff1a; 效果图&#xff1a; 代码图&#xff1a; 效果图&#xff1a; 3.重复渐变 代码&#xff1a; 效果图&#xff1a;

Python 学习完基础语法知识后,如何进一步提高?

入门Python后&#xff0c;就可以拿些小案例练手了&#xff0c;这时候千万不要傻乎乎地成天啃语法书。 编程是一门实践的手艺&#xff0c;讲究孰能生巧。不管是去手撸算法、或者照葫芦画瓢写几个小游戏都可以让你的Python突飞猛进。 之前看github比较多&#xff0c;推荐给大家…