一道算法题-二叉树的中序遍历_中序遍历为37,18,22,11,45,满足小根堆性质-程序员宅基地

技术标签： 算法  深度优先  动态规划  

最近项目比较紧，忙了将近半个月，再加上现在看的书，比较难整理出技术文章。趁着过年，重新梳理一下2022年的规划，把节奏调整正常。但立的每周完成一道算法题的flag还是要实现的。

二叉树中序遍历，如果用递归来做的话，有水题的嫌疑。不过好久没做过二叉树的题目了，用来练练手也是可以的。

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

图片

输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2：

输入：root = [] 输出：[] 示例 3：

输入：root = [1] 输出：[1] 示例 4：

图片

输入：root = [1,2] 输出：[2,1] 示例 5：

图片

输入：root = [1,null,2] 输出：[1,2]

提示：

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

解题思路

代码位置： https://github.com/shidawuhen/asap/blob/master/controller/algorithm/94-binary-tree-inorder-traversal.go

解这道题的前提是知晓中序遍历是一种怎样的遍历模式。通过下图可以看出，中序遍历需要先遍历到最左侧节点，然后访问其父节点，然后访问该父节点的右子节点的最左侧节点，如此形成一个循环模式。

图片

代码

按照该模式实现代码：

var nodeValue []int

func inorderTraversal(root *TreeNode) []int {
    
  nodeValue = make([]int, 0)
  if root == nil {
    
    return nodeValue
  }
  dsp(root)
  return nodeValue
}

func dsp(r *TreeNode) {
    
  //访问到最左侧节点
  if r.Left != nil {
    
    dsp(r.Left)
  }
  //访问其父节点
  nodeValue = append(nodeValue, r.Val)
  //访问父节点的右子节点。右子节点开始dsp后，会找到该节点的最左侧节点，进入循环。
  if r.Right != nil {
    
    dsp(r.Right)
  }
}

本来以为这个代码手到擒来，没想到忘了判断root是否为nil，提交的时候出现panic错误。所以说，再简单的题目，也应该细心的应对。
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shida219/article/details/122760947

智能推荐

我的JS每日一贴开始更新-程序员宅基地

文章浏览阅读149次。缘由经过今天在房X客的面试，我发现自己JS深深的不足，希望从现在开始，为了实现自己技术极客的目标，每天更新自己对于Javascript的技术点。积少成多，每天早上8点更新。 今天就更新关于JS函数相关的知识，希望能帮助更多的人。PS：房X客的面试官是一个技术极客。他微微秃顶，给我出的面试题前面四题考核的是我对面向对象的理解，对于基础知识的认识。然而我因为跨专业，懒惰的原因，并没..._js每日一贴

TIFF图像文件格式详解整理_tiff有多少万幅-程序员宅基地

文章浏览阅读1.5w次，点赞7次，收藏50次。1 什么是TIFF？TIFF是Tagged Image File Format的缩写。在现在的标准中，只有TIFF存在， 其他的提法已经舍弃不用了。做为一种标记语言，TIFF与其他文件格式最大的不同在于除了图像数据，它还可以记录很多图像的其他信息。它记录图像数据的方式也比较灵活， 理论上来说， 任何其他的图像格式都能为TIFF所用， 嵌入到TIFF里面。比如JPEG， Lossless JPE..._tiff有多少万幅

聊聊前端性有哪些性能优化方案_页面首屏渲染性能优化方案有哪些-程序员宅基地

文章浏览阅读295次。1、减少请求数量【合并】如果不进行文件合并，有如下3个隐患1、文件与文件之间有插入的上行请求，增加了N-1个网络延迟2、受丢包问题影响更严重3、经过代理服务器时可能会被断开但是，文件合并本身也有自己的问题1、首屏渲染问题2、缓存失效问题所以，对于文件合并，有如下改进建议1、公共库合并2、不同页面单独合并【图片处理】1、雪碧图CSS雪碧图是以前非常流行的技术，把网站上的一些图片整合到一张单独的图片中，可以减少网站的HTTP请求数量，但是当整合图片比较大时，一次加载比较慢。随着字体图_页面首屏渲染性能优化方案有哪些

mongodb-程序员宅基地

文章浏览阅读684次。发表时间：2010-09-07 > 猎头职位: 上海:Senior Software Engineer Java综合 mongodb由C＋＋写就，其名字来自humongous这个单词的中间部分，从名字可见其野心所在就是海量数据的处理。关于它的一个最简洁描述为：scalable, high-performance, open source, sche

赠书|刘皇叔竟是链圈“鼻祖”？Wow，钛合金*眼已被亮瞎-程序员宅基地

文章浏览阅读1k次。编辑 |kou刘皇叔翻出族谱，追溯整整十八代，才证明自己为汉室如果那时已有区块链技术，又会怎样？福利福利！本文节选自《区块链轻松上手——原理、源码、搭建与应用》文末免..._济川侯刘惠

oracle下wm_concat源码（ps:如果有些版本的oracle不支持此函数，只要执行下下面的语句即可）_oracle9中wm_concat函数源码-程序员宅基地

文章浏览阅读3.4k次，点赞2次，收藏2次。--创建wm_concat函数CREATE OR REPLACE TYPE WM_CONCAT_IMPLAUTHID CURRENT_USER AS OBJECT( CURR_STR CLOB,--VARCHAR2(32767), STATIC FUNCTION ODCIAGGREGATEINITIALIZE(SCTX IN OUT WM_CONCAT_IMPL)_oracle9中wm_concat函数源码

随便推点

微电子新手入门之Cadence常用仿真——NMOS管的C-V曲线_nmos电容随栅源电压变化曲线-程序员宅基地

文章浏览阅读1.3w次，点赞7次，收藏63次。C -V 特性曲线即是测量栅端输入电容跟栅电压的关系。考虑电容特性：AC下Iac/Vac=2πfC ，如果令交流电压Vac =1V，选择频率 f （0.16 Hz）使得 2πf=1rad/s ，这时候得到的交流电流就是电容值。进行AC设置，设置好工作频率，对栅极偏压vg进行扫描，从-1V~1V之间。ac仿真结束后，将探针0电流取值到计算器当中： 同样的，将探针1..._nmos电容随栅源电压变化曲线

windows10安装无CPU版本的清华镜像pytorch，以及解决CondaHTTPError和ImportError: No module named 'torch'的问题_no module named 'torchsummary' 镜像安装-程序员宅基地

文章浏览阅读3.1w次，点赞11次，收藏23次。安装过程耗时两天，终于修成正果。先列出最后成功的安装命令：（我的python版本3.6）​conda install pytorch-cpu=0.3.1 ​conda install torchvision-cpu过程如下：anaconda我已经下载安装好了的，这个倒是很顺利，后面就是安装pytorch折腾了很久。先是使用下载好的pytorch-cpu压缩包进行..._no module named 'torchsummary' 镜像安装

FMEA-MSR 步骤四：失效分析_失效链、失效网-程序员宅基地

文章浏览阅读2.7k次，点赞3次，收藏7次。目的在相关的场景下,FMEA-MSR的失效分析旨在说明导致最终影响的事件链。MEA-MSR失效分析的主要目标：● 建立失效链● 失效起因、监视、系统响应、减轻的失效影响● 使用参数图或失效网识别产品失效起因● 顾客与供应商之间的协作(失效影响)● FMEA表格中失效文件化和风险分析步骤的基础（点击链接进入官网领取软件试用）失效场景失效场景由相关操作条件的描述组成,在这些条件中,故障导致错误。行为并且可能导致最终系统状态(失效影响)的事件序列(系统状态)。它的起点为确定的失效起因,而其_失效链、失效网

Unity5.5+easytouch5双摇杆控制角色移动-程序员宅基地

文章浏览阅读697次。第一步：新建两个Joystick，分别改名LeftJoyStick和RightJoyStick在LeftJoyStick的ETC Joystick-Axes properties中的Horizontal axis-General setting中将要控制的人物Player拖入框中，action选translate,Affected action选 X到现在位置，就可以通过左摇..._easytouch 控制物体移动旋转

基于STM32的MDK软件仿真输出PWM波形_基于stm32的推箱子输出波形数据-程序员宅基地

文章浏览阅读7k次，点赞11次，收藏70次。文章目录一、PWM相关1、PWM是什么2、PWM原理3、PWM应用4、PWM信号输出二、实验相关1、实验要求2、实验环境3、实验结果2、用STM32F103的DAC功能完成以下波形输出，用示波器观察波形，并用蜂鸣器或手机耳机收听输出声音效果、感受歌曲的音质差异。1）输出一个周期2khz的正弦波（循环）。此波形驱动作用至蜂鸣器或喇叭，会呈现一个“滴…”的单音；2）将一段数字音频歌曲数据转换为模拟音频波形输出（循环）。提示：首先用音频制作工具制作一段数字化的2khz正弦波wav文件、转换一首你喜欢的歌曲_基于stm32的推箱子输出波形数据

Ext JS 4.1.1 RC1 发布_getvisibleheaderclosest.toindex()-程序员宅基地

文章浏览阅读2.2k次。原文：http://www.sencha.com/forum/showthread.php?205564-Ext-JS-4.1.1-RC1-Now-AvailableWe are pleased to announce today the availability of Ext JS 4.1.1 RC1.http://cdn.sencha.io/ext-4.1.1-rc1.zipOf partic_getvisibleheaderclosest.toindex()

推荐文章

热门文章

相关标签