博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
算法:二叉搜索树的后序遍历序列
阅读量:6418 次
发布时间:2019-06-23

本文共 1255 字,大约阅读时间需要 4 分钟。

 

* @Description 二叉搜索树的后序遍历序列  * @问题: 题目描述  * 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。  * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。  * @思路:   1:判断长度极端情况,为零则直接返回false   2:判断为节点小于等于头节点的极端情况;   3:找到中间根节点,大于尾部节点的时候break;   4:直接根据二叉树后序遍历,右子树都大于根节点,小于则直接返回false;再递归左右子树;

 

 

package LG.nowcoder;/** * @Author liguo * @Description 二叉搜索树的后序遍历序列 * @问题: 题目描述 * 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 * @思路:1:判断长度极端情况,为零则直接返回false2:判断为节点小于等于头节点的极端情况;3:找到中间根节点,大于尾部节点的时候break;4:直接根据二叉树后序遍历,右子树都大于根节点,小于则直接返回false;再递归左右子树; * @Data 2018-09-23 23:52 */public class Solution25 {    public boolean VerifySquenceOfBST(int [] sequence) {        if(sequence.length == 0) return false;        return IsTreeBST(sequence, 0, sequence.length-1);    }    public boolean IsTreeBST(int [] sequence,int start,int end ){        if(end <= start) return true;        int i = start;        //找到比根大的坐标;        for (; i < end; i++) {            if(sequence[i] > sequence[end]) break;        }        //从根到尾部都应该比尾部的节点大;        for (int j = i; j < end; j++) {            if(sequence[j] < sequence[end]) return false;        }        return IsTreeBST(sequence, start, i-1) && IsTreeBST(sequence, i, end-1);    }}
View Code

 

转载于:https://www.cnblogs.com/liguo-wang/p/9694389.html

你可能感兴趣的文章
代理模式
查看>>
javaweb学习总结(二十四)——jsp传统标签开发
查看>>
让script的type属性等于text/html
查看>>
[Docker] Docker Machine intro
查看>>
HA 高可用软件系统保养指南
查看>>
linux 文件系统sysvinit 流程分析
查看>>
体素科技:2018年,算法驱动下的医学影像分析进展
查看>>
Vue 折腾记 - (8) 写一个挺靠谱的多地区选择组件
查看>>
VS Code折腾记 - (3) 多图解VSCode基础功能
查看>>
再不懂区块链,你就OUT了!
查看>>
教你玩转自定义View—手撸一个倒计时控件如此简单
查看>>
『翻译』Node.js 调试
查看>>
我的iOS开发之路总结(更新啦~)
查看>>
Java NIO之拥抱Path和Files
查看>>
微信原图泄露的只能是 Exif ,你的隐私不在这!!!
查看>>
微信小程序教学第三章(含视频):小程序中级实战教程:列表篇-页面逻辑处理...
查看>>
页面间通信与数据共享解决方案简析
查看>>
Swift 中 Substrings 与 String
查看>>
作为一个开源软件的作者是一种什么样的感受?
查看>>
移动端适配知识你到底知多少
查看>>