当前位置: 首页 > news >正文

二叉树的遍历方式和子问题思路

        

目录

        二叉树的遍历:

        前序遍历:

       

       中序遍历:    

        后序遍历:

  二叉树的基本操作:

        求树的结点个数(递归遍历思路):

        求树的结点个数(子问题思路):

      求树的叶子结点个数:

        求第K层结点个数:

        求树的高度:

      判断值为value的结点是否存在:


        下述代码并不是创建二叉树的方式,而是模拟创建一颗二叉树来实现二叉树的遍历方式和体验子问题思路。

public class BinaryTree {static class TreeNode {public char val;//存储左孩子节点的引用public TreeNode left;//存储右孩子节点的引用public TreeNode right;public TreeNode(char val) {this.val = val;}}public TreeNode createTree() {TreeNode A = new TreeNode('A');TreeNode B = new TreeNode('B');TreeNode C = new TreeNode('C');TreeNode D = new TreeNode('D');TreeNode E = new TreeNode('E');TreeNode F = new TreeNode('F');TreeNode G = new TreeNode('G');TreeNode H = new TreeNode('H');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;E.right = H;return A;}}

         构成的树如图:

        

        二叉树的遍历:

        前序遍历:

        此方法访问结点形式:

        根 --- > 左子树 --- > 右子树

        代码实现:

 public void preOrder(TreeNode root) {if(root == null) {return;}System.out.print(root.val+" ");preOrder(root.left);preOrder(root.right);}

         代码运行结果:

        

       

       中序遍历:    

        此方法访问结点形式:

         左子树 --- >根--- > 右子树

         代码实现:

 public void inOrder(TreeNode root) {if(root == null) {return;}inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}

         代码运行结果:

        

        

        后序遍历:

          此方法访问结点形式:

         左子树 --- > 右子树 --- >根

         代码实现:

 public void posOrder(TreeNode root) {if(root == null) {return;}posOrder(root.left);posOrder(root.right);System.out.print(root.val+" ");}

        代码运行结果:

        

         

        这三种遍历方式都是通过递归函数本身来遍历的,通过不断往左和往右边 “递” ,遇到空时return开始 “归” ,所以,分析二叉树递归时可以一直往左递归下去先分析,再往右分析。

        

        

  二叉树的基本操作:

        求树的结点个数(递归遍历思路):

                代码实现:

 public int countNode = 0;public void nodeSize(TreeNode root) {if(root == null) {return;}countNode++;nodeSize(root.left);nodeSize(root.right);}

        代码运行结果:

         

         可以看到,求得的结点个数为8是正确的。这种方法是通过边递归边求和的方法。

        

        求树的结点个数(子问题思路):

        对于一棵树,这样分析:

        一棵树的结点数 = 左子树结点数 + 右子树结点数 + 1。

        要是对一棵树所有结点都这样分析,就可以得到:

 public int nodeSize2(TreeNode root) {if(root == null) {return 0;}return nodeSize2(root.left) + nodeSize2(root.right) + 1;}

代码运行结果:

        

        可以得到结点数也是8 ,子问题思路对于解决二叉树问题很重要,后续也是针对二叉树的子问题思路来解决问题。

        

      求树的叶子结点个数:

        对于一棵树,这样分析:

        一棵树的叶子结点数 = 左子树叶子结点数 + 右子树叶子结点数 。

 public int getLeaf(TreeNode root) {if(root == null) {return 0;}if(root.left == null && root.right == null) {return 1;}else {return getLeaf(root.left) + getLeaf(root.right);}}

        求第K层结点个数:

        对于一棵树,这样分析:

        假如要求根为root的树的第K层结点个数:

        以子问题分析得到:

       整棵树的第K层结点数 = root.left 的第(K-1)层结点数 +  root.right 的第(K-1)层结点数 

        实现代码:

 public int getKLeve(TreeNode root,int k) {if(root == null) {return 0;}if(k == 1) {return 1;}return getKLeve(root.left,k-1) + getKLeve(root.right,k-1);}

        

        求树的高度:

         对于一棵树,  以子问题分析得到:

        整棵树的高度 = 取 左子树与右子树 最大的值 + 1.

        代码实现:

public int getHight(TreeNode root) {if(root == null) {return 0;}int leftH = getHight(root.left);int rightH = getHight(root.right);return leftH > rightH ? leftH+1 : rightH + 1;}

        

      判断值为value的结点是否存在:

        对于一棵树,分析得到:

        先判断左子树是否存在,再判断右子树是否存在,寻找过程中如果找到了就返回当前结点。

        代码实现:

public TreeNode find(TreeNode root,char value) {if(root == null) {return null;}if(root.val == value) {return root;}TreeNode leftval = find(root.left,value);if(leftval != null) {return leftval;}TreeNode rightval = find(root.right,value);if(rightval != null) {return rightval;}return null;}

        

相关文章:

二叉树的遍历方式和子问题思路

目录 二叉树的遍历: 前序遍历: 中序遍历: 后序遍历: 二叉树的基本操作: 求树的结点个数(递归遍历思路): 求树的结点个数(子问题思路): 求树的…...

运用Deek Seeker协助数据分析

我的数据源有两张表,一个是每日销售表(字段有日期、产品名称、实际销量),一个是每月目标表(字段有年度月份、产品名称、目标销量);我的需求是,按月、按年来统计每个产品的目标完成情况请问用PowerBl进行分析,应该如何建立数据模型…...

服务器之连接简介(Detailed Explanation of Server Connection)

一台服务器最大能支持多少连接?一台客户端机器最多能发起多少条连接?? 我们知道TCP连接,从根本上看其实就是client和server端在内存中维护的一组【socket内核对象】(这里也对应着TCP四元组:源IP、源端口、…...

低空经济:开启未来空中生活的全新蓝海

引言 随着科技的进步,我们不再仅仅依赖地面交通和传统物流。你是否曾幻想过,未来的某一天,快递、外卖可以像魔法一样直接从空中送到你手中?或者,你能乘坐小型飞行器,快速穿梭于城市之间,告别拥堵…...

主动视觉可能就是你所需要的:在双臂机器人操作中探索主动视觉

AV-ALOHA 系统使用用于 AV 的 VR 耳机实现直观的数据收集,并且 用于作的 VR 控制器或引线臂。这有助于捕捉全身和头部 远程作我们的真实和模拟系统的运动,记录来自 6 个的视频 不同的摄像头,并为我们的 AV 仿制学习策略提供训练数据。 加州大…...

洛谷 P6419 COCI2014/2015 #1 Kamp 题解

题意 一颗树 n n n 个点, n − 1 n-1 n−1 条边,经过每条边都要花费一定的时间,任意两个点都是联通的。 有 k k k 个人(分布在 k k k 个不同的点)要集中到一个点举行聚会。 聚会结束后需要一辆车从举行聚会的这点…...

在 Vue 项目中使用 SQLite 数据库的基础应用

目录 一、环境准备二、数据库连接与操作1. 创建数据库连接2. 创建表3. 插入数据4. 查询数据5. 更新数据6. 删除数据 三、在 Vue 组件中使用 SQLite 一、环境准备 安装 Node.js 和 npm:确保已安装 Node.js 和 npm。 创建 Vue 项目:使用 Vue CLI 创建一个…...

AI会话问答的页面滚动处理(参考deepseek页面效果)

近期在接入deepseekR1的深度思考,研究了下deepseek官网的滚动效果,大概如下:用户发出消息后,自动滚动到页面最底部,让最新消息展示在视野中,这时候,我们先处理一次滚动: const scrol…...

GRN前沿:DGCGRN:基于有向图卷积网络的基因调控网络推理

1.论文原名:Inference of gene regulatory networks based on directed graph convolutional networks 2.发表日期:2024 DGCGRN框架 中心节点和节点的构建 局部增强策略 1. 问题背景 在基因调控网络中,许多节点的连接度较低(即…...

MongoDB 入门操作指南

文章目录 MongoDB 入门操作指南1. 连接到 MongoDB 数据库2. 查看当前数据库3. 显示所有数据库4. 切换或创建数据库5. 查看当前数据库中的所有集合6. 创建集合7. 插入文档插入单个文档插入多个文档 8. 查询文档查询所有文档查询匹配条件的文档格式化查询输出 9. 更新文档更新单个…...

共享设备管理难?MDM助力Kiosk模式一键部署

目录 1. 简化设备部署与配置:实现一键式部署 2. 自动化应用更新与内容推送:确保设备始终保持最新状态 3. 权限控制与设备安全:防止滥用与数据泄露 4. 远程管理与故障诊断:保障设备长期稳定运行 5. 数据分析与报告&#xff1a…...

HttpClient-Java程序中发送Http请求

配置 <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient</artifactId><version>4.5.13</version> </dependency> ps:aliyun-sdk-oss中已引入上述配置 HttpClient的核心API&#xff1a; Htt…...

硬件-电源-隔离与非隔离的区别

文章目录 一&#xff1a;隔离电源与非隔离电源1.1 充电器触电新闻1.2 电路拓扑1.3 隔离电源与非隔离电源的优缺点1.3 隔离电源与非隔离电源的选择1.3.1 隔离电源1.3.2 非隔离电源 二&#xff1a;注意事项2.1 隔离电源结构图2.1 隔离耐压测试方法 三&#xff1a;感悟道友&#x…...

Kubernetes 最佳实践:Top 10 常见 DevOps/SRE 面试问题及答案

1. 如何在 Kubernetes 中设置资源请求和限制&#xff1f; 资源请求确保容器有最小资源量&#xff08;CPU/内存&#xff09;&#xff0c;而限制则强制容器消耗的最大资源量。这有助于高效资源分配并防止资源争用。 示例&#xff1a; resources:requests:memory: "256Mi&…...

Training for Computer Use

Training for Computer Use 核心事件&#xff1a;多家科技公司推出能操控计算机的智能体&#xff0c;字节跳动和清华大学团队引入UI - TARS模型&#xff0c;展示了训练模型实现计算机操控能力的新成果。 UI - TARS模型 基本信息&#xff1a;是视觉 - 语言模型Qwen2 - VL的微调版…...

PH热榜 | 2025-02-14

1. Beatoven.ai 标语&#xff1a;能创作完美背景音乐的AI作曲家 介绍&#xff1a;Beatoven.ai 能根据简单的提示生成惊艳的背景音乐&#xff0c;用于你的内容创作。它是由世界各地的真实音乐家倾力打造&#xff08;并使用了大量数据&#xff09;。无需任何音乐专业知识&#…...

工业物联网远程监控系统优化方案,基于巨控GRM553Y-CHE

工业物联网远程监控系统优化方案 ——基于巨控GRM553Y-CHE的西门子S7-1500 PLC多站点无线集成方案 1. 项目背景与概述 巨控科技作为工业物联网解决方案提供商&#xff0c;专注于PLC无线通信与远程监控技术研发&#xff0c;其YunPLC安全平台已服务超30,000工业终端&#xff0c…...

报名丨Computer useVoice Agent :使用 TEN 搭建你的 Mac Assistant

与 TEN 相聚在「LET’S VISION 2025」大会&#xff0c;欢迎来展位上跟我们交流。这次我们还准备了一场聚焦「computer use」的工作坊&#xff0c;功能新鲜上线&#xff0c;线下首波体验&#xff01; &#x1f4c5; TEN 展位&#xff1a;2025年3月1日-2日 TEN workshop&#x…...

Flutter 中的生命周期

在 Flutter 中&#xff0c;StatefulWidget 和 StatelessWidget 这两种 Widget 的生命周期不同&#xff0c;主要关注的是 StatefulWidget&#xff0c;因为它涉及到状态的管理和更新。 StatefulWidget 的生命周期&#xff1a; 1. 创建阶段 (Create) createState()&#xff1a;…...

深度整理总结MySQL——redoLog日志工作原理

redo log的工作原理 前言概念为什么需要redo log修改undo页面,会记录对应的redo log吗redo log 和undo log 区别在哪什么是WAL技术redo log要写入磁盘,数据也要写入磁盘,为什么多此一举产生的redo log直接写入磁盘吗redo log 什么时候刷盘innodb_flush_log_at_trx_commit 参数参…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...