二叉树算法题

news/2024/4/21 13:16:17/文章来源:https://blog.csdn.net/qq_58578599/article/details/136571847

树的初始化

类包含左右节点属性以及val值。

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}

二叉树的中序遍历。

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();dfs(res,root);return res;}void dfs(List<Integer> res, TreeNode root) {if(root==null) {return;}//按照 左-打印-右的方式遍历dfs(res,root.left);res.add(root.val);dfs(res,root.right);}

二叉树的中序遍历2。

    public static List<Integer> inorderTraversal2(TreeNode root){//中序遍历List<Integer> res = new ArrayList<>();Deque<Object> stack = new LinkedList<>();if(root == null) return res;stack.push("WHITE");stack.push(root);while(!stack.isEmpty()){TreeNode node = (TreeNode)stack.pop();String color = (String)stack.pop();if (node == null) continue;if(color == "WHITE"){stack.push("WHITE");stack.push(node.right);stack.push("GRAY");stack.push(node);stack.push("WHITE");stack.push(node.left);}else{res.add(node.val);}}return res;}

翻转二叉树。

    public static TreeNode invertTree(TreeNode root) {//递归函数的终止条件,节点为空时返回if(root==null) {return null;}//下面三句是将当前节点的左右子树交换TreeNode tmp = root.right;root.right = root.left;root.left = tmp;//递归交换当前节点的 左子树invertTree(root.left);//递归交换当前节点的 右子树invertTree(root.right);//函数返回时就表示当前这个节点,以及它的左右子树//都已经交换完了return root;}

二叉树的最大深度

    public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}

测试类 生成了7种不一样的树。

    public static void main(String[] args) {//7个不同的树TreeNode root1 = null; // 空树TreeNode root2 = new TreeNode(1); // 只有根节点的树TreeNode root3 = new TreeNode(1); // 完全平衡二叉树root3.left = new TreeNode(2);root3.right = new TreeNode(3);root3.left.left = new TreeNode(4);root3.left.right = new TreeNode(5);TreeNode root4 = new TreeNode(1); // 非平衡二叉树root4.left = new TreeNode(2);root4.left.left = new TreeNode(3);root4.left.left.left = new TreeNode(4);root4.left.left.left.left = new TreeNode(5);TreeNode root5 = new TreeNode(1); // 只有左子树的树root5.left = new TreeNode(2);TreeNode root6 = new TreeNode(1); // 只有右子树的树root6.right = new TreeNode(2);TreeNode root7 = new TreeNode(1); // 多层深度的树root7.left = new TreeNode(2);root7.right = new TreeNode(3);root7.left.left = new TreeNode(4);root7.right.right = new TreeNode(5);invertTree(root7);System.out.println(inorderTraversal2(root7));}

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

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

相关文章

数字音频工作站(DAW)fl studio 21 for mac 21.2.3.3586中文版图文安装教程

随着音乐制作行业的不断发展&#xff0c;越来越多的音乐人和制作人开始使用数字音频工作站&#xff08;DAW&#xff09;来创作和制作音乐。其中FL Studio 21是一个备受欢迎的选择&#xff0c;因为它提供了强大的音乐制作工具和易于使用的界面。 然而&#xff0c;一直以来&…

鸡肋的Git

1.前言 对于大多数开发人员来说&#xff0c;我们大多数在学习或者工作过程中只关注核心部分&#xff0c;比如说学习Java&#xff0c;可能对于大多数人而言一开始都是从Java基础学起&#xff0c;然后408&#xff0c;Spring&#xff0c;中间件等&#xff0c;当你发现很多高深的技…

循序渐进丨MogDB 数据库新特性之SQL PATCH绑定执行计划

1 SQL PATCH 熟悉 Oracle 的DBA都知道&#xff0c;生产系统出现性能问题时&#xff0c;往往是SQL走错了执行计划&#xff0c;紧急情况下&#xff0c;无法及时修改应用代码&#xff0c;DBA可以采用多种方式针对于某类SQL进行执行计划绑定&#xff0c;比如SQL Profile、SPM、SQL …

SpringBootWeb(接收请求数据,返回响应结果,分层解耦,Spring的IOCDI)【详解】

目录 一、接收请求数据 1. 接收表单参数 1.原始方式【了解】 2.SpringBoot方式 3.参数名不一致RequestParam 2.实体参数 1.简单实体对象 2.复杂实体对象 3.数组集合参数 4.日期参数 3. JSON参数 1.Postman发送JSON数据 2.服务端接收JSON数据 4. 路径参数(rest风格…

论文阅读之Multimodal Chain-of-Thought Reasoning in Language Models

文章目录 简介摘要引言多模态思维链推理的挑战多模态CoT框架多模态CoT模型架构细节编码模块融合模块解码模块 实验结果总结 简介 本文主要对2023一篇论文《Multimodal Chain-of-Thought Reasoning in Language Models》主要内容进行介绍。 摘要 大型语言模型&#xff08;LLM…

STM32FreeRTOS任务通知(STM32cube高效开发)

文章目录 一、任务通知(一&#xff09;任务通知概述1、任务通知可模拟队列和信号量2、任务通知优势和局限性 (二) 任务通知函数1、xTaskNotify&#xff08;&#xff09;发送通知值不返回先前通知值的函数2、xTaskNotifyFromISR&#xff08;&#xff09;发送通知函数ISR版本3、x…

【npm】前端工程项目配置文件package.json详解

简言 详细介绍了package.json中每个字段的作用。 package.json 本文档将为您介绍 package.json 文件的所有要求。它必须是实际的 JSON&#xff0c;而不仅仅是 JavaScript 对象文字。 如果你要发布你的项目&#xff0c;这是一个特别重要的文件&#xff0c;其中name和version是…

stable diffusion 原理是什么?

“ 这篇文章主要介绍了Stable Diffusion&#xff0c;这是一种用于AI绘画的算法&#xff0c;它是由CompVis和Runway团队在2021年12月提出的“潜在扩散模型”&#xff08;LDM/Latent Diffusion Model&#xff09;的变体&#xff0c;基于2015年提出的扩散模型&#xff08;DM/Diffu…

SpringCloud Ribbon 负载均衡服务调用

一、前言 接下来是开展一系列的 SpringCloud 的学习之旅&#xff0c;从传统的模块之间调用&#xff0c;一步步的升级为 SpringCloud 模块之间的调用&#xff0c;此篇文章为第三篇&#xff0c;即介绍 Ribbon 负载均衡服务调用 二、概述 2.1 Ribbon 是什么 Spring Cloud Ribbon…

滤波器:工作原理和分类及应用领域?|深圳比创达电子EMC

滤波器在电子领域中扮演着重要的角色&#xff0c;用于处理信号、抑制噪声以及滤除干扰。本文将详细介绍滤波器的工作原理、分类以及在各个应用领域中的具体应用。 一、滤波器的定义和作用 滤波器是一种电子设备&#xff0c;用于选择性地通过或阻塞特定频率范围内的信号。其主…

数智化时代的新潮流:企业如何利用数据飞轮驱动增长?_光点科技

随着数据中台理念的逐渐“降温”&#xff0c;企业数智化的探索并未停歇。反而&#xff0c;数据飞轮成为了新的焦点&#xff0c;它承诺为企业带来更紧密的业务与数据结合&#xff0c;从而推动持续的增长。本文将探讨企业如何利用数据飞轮的概念&#xff0c;赋能业务&#xff0c;…

实现QT中qDebug()的日志重定向

背景&#xff1a; 在项目开发过程中&#xff0c;为了方便分析和排查问题&#xff0c;我们需要将原本输出到控制台的调试信息写入日志文件&#xff0c;进行持久化存储&#xff0c;还可以实现日志分级等。 日志输出格式&#xff1a; 我们需要的格式包括以下内容&#xff1a; 1.…

云上攻防-云原生篇K8s安全实战场景攻击Pod污点Taint横向移动容器逃逸

知识点 1、云原生-K8s安全-横向移动-污点Taint 2、云原生-K8s安全-Kubernetes实战场景 章节点&#xff1a; 云场景攻防&#xff1a;公有云&#xff0c;私有云&#xff0c;混合云&#xff0c;虚拟化集群&#xff0c;云桌面等 云厂商攻防&#xff1a;阿里云&#xff0c;腾讯云&…

Graphpad Prism10.2.1(395) 安装教程 (含Win/Mac版)

GraphPad Prism GraphPad Prism是一款非常专业强大的科研医学生物数据处理绘图软件&#xff0c;它可以将科学图形、综合曲线拟合&#xff08;非线性回归&#xff09;、可理解的统计数据、数据组织结合在一起&#xff0c;除了最基本的数据统计分析外&#xff0c;还能自动生成统…

什么是物联网?物联网如何工作?

物联网到底是什么&#xff1f; 物联网(Internet of Things&#xff0c;IoT)的概念最早于1999年被提出&#xff0c;官方解释为“万物相连的互联网”&#xff0c;是在互联网基础上延伸和扩展&#xff0c;将各种信息传感设备与网络结合起来而形成的一个巨大网络&#xff0c;可以实…

USB2.0设备检测过程信号分析

1.简介 USB设备接入的Hub端口负责检测USB2.0设备是否存在和确定USB2.0设备的速度。检测设备是否存在和确定设备速度涉及一系列的信号交互&#xff0c;下面将分析该过程。 2.硬件 USB低速设备和全速/高速设备的连接器在硬件结构上有所不同&#xff0c;而主机或者Hub接收端连接…

复杂业务场景下,如何优雅的使用设计模式来优化代码?

1、引言 本文以一个实际案例来介绍在解决业务需求的路上&#xff0c;如何通过常用的设计模式来逐级优化我们的代码&#xff0c;以把我们所了解的到设计模式真实的应用于实战。 2、背景 假定我们现在有一个订单流程管理系统&#xff0c;这个系统对于用户发起的一笔订单&#…

【IEEE列表会议】IEEE第三届信息与通信工程国际会议国际会议(JCICE 2024)

会议简介 Brief Introduction 2024年第三届信息与通信工程国际会议国际会议 (JCICE 2024) 会议时间&#xff1a;2024年5月10日-12日 召开地点&#xff1a;中国福州 大会官网&#xff1a;JCICE 2024-2024 International Joint Conference on Information and Communication Engi…

揭秘Web缓存:提升网站性能与用户体验

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

专题一 - 双指针 - leetcode 18. 四数之和 - 中等难度

leetcode 18. 四数之和 leetcode 18. 四数之和 | 中等1. 题目详情1. 原题链接2. 基础框架 2. 解题思路1. 题目分析2. 算法原理3. 时间复杂度 3. 代码实现 leetcode 18. 四数之和 | 中等 1. 题目详情 给你一个由 n 个整数组成的数组 nums &#xff0c;和一个目标值 target 。请…