【剑指OFFER】面试题33. 二叉搜索树的后序遍历序列
发布日期:2021-06-29 19:46:22
浏览次数:2
分类:技术文章
本文共 1030 字,大约阅读时间需要 3 分钟。
题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5 / \ 2 6 / \ 1 3
示例 1:
输入: [1,6,3,2,5]
输出: false示例 2:
输入: [1,3,2,6,5]
输出: true提示:
数组长度 <= 1000
答案:
class Solution { public boolean verifyPostorder(int[] postorder) { //递归判断左子树右子树是否满足条件 if(postorder.length == 0 || postorder.length == 1) return true; int index = postorder.length - 1; for(int i = 0; i < postorder.length; i++){ if(postorder[i] > postorder[postorder.length - 1] && index == postorder.length - 1){ index = i; } if(i > index){ if(postorder[i] < postorder[postorder.length - 1]) return false; } } int[] p1 = new int[index]; int[] p2 = new int[postorder.length - index - 1]; System.arraycopy(postorder, 0, p1, 0, index); System.arraycopy(postorder, index, p2, 0, postorder.length - index - 1); return verifyPostorder(p1) && verifyPostorder(p2); }}
转载地址:https://darkness.blog.csdn.net/article/details/105810901 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年05月02日 12时15分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
MPG(MPEG2 Program Stream)格式解析
2019-04-30
Gstreamer学习笔记(4):pad定义、连接、流动
2019-04-30
Gstreamer 学习笔记(3):GstElement状态
2019-04-30
Gstreamer学习笔记(9):message, even, signal区别
2019-04-30
Gstreamer 学习笔记(10):Gstvideodecoder
2019-04-30
Gstreamer学习笔记(11):typefind功能流程简单分析
2019-04-30
在MPEG之前
2019-04-30
MPEG-1
2019-04-30
MPEG-1中I、B、P帧的基本编码原理
2019-04-30
MPEG-2
2019-04-30
MPEG-2 数据位流与视像质量可变编码
2019-04-30
H.264/AVC简介
2019-04-30
H.264/AVC 的分层结构与画面划分
2019-04-30
H.264/AVC 中的宏块、片、帧
2019-04-30
H.264/AVC 三种配置和帧内预测
2019-04-30
H.264/AVC 帧间预测
2019-04-30
H.264/AVC 的各大主流编解码器
2019-04-30
【H264/AVC 句法和语义详解】(一):句法元素分层结构
2019-04-30
【H.264/AVC 句法和语义详解】(二):h264码流格式与NALU详解一
2019-04-30