当前栏目
二叉树的后序遍历序列
前言
有一个整数数组,如何判断该数组是不是某个二叉树的后序遍历结果?本文就跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文。
思路分析
我们通过一个例子来分析这个问题,如下所示为一颗二叉树。
通过之前文章的学习(二叉树的后序遍历),我们可以很快看出这颗树的后序遍历序列为: [5, 7, 6, 9, 11, 10, 8],通过观察后我们发现最后一个数字为二叉树的根节点,数组中前面的数字可以分为两部分:
第一部分是左子树节点的值,它们都比根节点的值小
第二部分是右子树节点的值,它们都比根节点的值大
在上面的后序遍历结果数组中,前3个数字5、7、6都比根节点8小,是它的左子树节点;后3个数字9、11、10都比根节点8大,是它的右子树节点。
那么,我们就可以用同样的方法来确定数组每一部分对应的子树的结构。
数组5, 7, 6,最后一个数字6是左子树的根节点的值。数字5比6小,是6的左子节点,7则是它的右子节点
数组9, 11, 10,最后一个数字10是左子树的根节点的值。数字9比10小,是10的左子节点,11则是它的右子节点
实现思路
通过上面的分析,我们便可以总结出实现思路了。
最后一项一定是根节点,从根节点前面的值中寻找左、右子树的分界点
定义指针leftIndex,前半部分一定是它的左子树,每个节点的值都比根节点小
leftIndex默认从0开始,逐渐递增,寻找比根节点大的值,便是它们的分界点
定义指针rightIndex,后半部分一定是它的右子树,每个节点的值都比根节点大。
rightIndex从分界点开始找(默认从leftIndex位置开始),如果有比根节点小的值,那么这个序列一定不属于二叉树的后序遍历序列
如果leftIndex指针离开了起始位置(0),证明它的左子节点还没找完,需要重复执行上述过程继续查找(递归寻找到数组的leftIndex位置)
如果leftIndex指针没有到达数组末尾,证明它的右子节点还没找完,需要重复执行上述过程继续查找(从leftIndex+1位置开始递归)
返回左、右子树的递归校验结果(两者都为true则表示这个序列为二叉树的后序遍历序列)
实现代码
捋清楚思路后,我们便可以顺利的写出代码了。
测试用例
接下来我们将思路分析中所列举的例子代入上述代码,来验证下我们的代码能否正确执行。
我们再列举一个错误的例子,来验证下它能否正确判断。
示例代码
本文用到的代码完整版请移步:
- TreeOperate.ts
- TreeOperate-test.ts
相关文章
- css3美化半个字符 代码教程
- 哈啰 Quark Design 正式开源,新一代跨技术栈前端组件库
- 深度分析React源码中的合成事件2
- 手写一个react,看透react运行机制2
- 从react源码看hooks的原理2
- react的useState源码分析2
- react源码分析:组件的创建和更新2
- react源码解析14.手写hooks2
- react源码解析13.hooks源码2
- 刷完15道js版dp题,面试再也不怕了2
- 前端工程师leetcode算法面试必备-简单的二叉树
- 前端面试指南之JS面试题总结2
- 大厂前端面试考什么?2
- 前端面试前端性能优化篇2
- 这样回答前端面试题才能拿到offer2
- Linux下安装Node.js并国内源(淘宝)
- Vue & Element
- 前端必会react面试题合集2
- 前端react面试题(必备)2
- 如何两天时间上线一款AI应用?