算法：二叉搜索树的后序遍历序列

女爷i 2024-04-08 11:10 31阅读 0赞

![7af891dd598df1b80808efd17611b8ad.jpeg][]

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

5

/ \\

2 6

/ \\

1 3

## 示例 ##

*  输入: \[1,3,2,6,5\]
 *  输出: true

## 提示 ##

*  数组长度 <= 1000

## 方法：递归分治 ##

**后序遍历：**

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：【遍历左子树|遍历右子树|访问根结点】。

**二叉搜索树：**

在二叉搜索树中：

*  若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
 *  若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
 *  任意结点的左、右子树也分别为二叉搜索树。

**代码如下：**

![a956fba8bc60873f1fa57abf90af9f1d.jpeg][]

## 复杂度分析 ##

*  时间复杂度：O(N的2次方)， 每次调用 compare(i,j) 减去一个根节点，因此递归占用 O(N) ；最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N) 。
 *  空间复杂度：O(N)，最差情况下（即当树退化为链表），递归深度将达到 N 。

## END ##

世上无难事，只要肯攀登，赠友人。

本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！

[7af891dd598df1b80808efd17611b8ad.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e5f370e96fae4ca1abde606b7297ceb5.jpeg
[a956fba8bc60873f1fa57abf90af9f1d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/832a3e34b76a4fc2812eade653bac71a.jpeg

发表评论取消回复

表情：

评论列表（有 0 条评论，31人围观）

还没有评论，来说两句吧...

相关阅读

相关算法：二叉搜索树的后序遍历序列

![7af891dd598df1b80808efd17611b8ad.jpeg][] 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否

女爷i/ 2024年04月08日 11:10/ 0 赞/ 32 阅读

相关二叉搜索树+前序遍历 -> 后序遍历

[sdut原题链接][sdut] 迷失の搜索树 Time Limit: 1000MS Memory Limit: 65536KB Problem Description

末蓝、/ 2022年07月12日 03:14/ 0 赞/ 292 阅读

相关二叉搜索树的后序遍历序列

面试题24：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字互不相同 //二叉搜

谁借莪１个温暖的怀抱￠/ 2022年06月17日 06:20/ 0 赞/ 124 阅读

相关二叉搜索树的后序遍历序列

![这里写图片描述][70] public class Solution { //方法二，非递归，找规律 public b

叁歲伎倆/ 2022年05月25日 03:08/ 0 赞/ 105 阅读

相关二叉搜索树的后序遍历序列 java

二叉搜索树的后序遍历序列 java 题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两

蔚落/ 2022年05月11日 15:20/ 0 赞/ 136 阅读

相关二叉搜索树后序遍历序列

题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思路二叉搜

短命女/ 2022年05月11日 04:12/ 0 赞/ 174 阅读

相关二叉搜索树的后序遍历序列

[二叉搜索树的后序遍历序列][Link 1] 题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的

末蓝、/ 2022年03月25日 15:29/ 0 赞/ 167 阅读

相关二叉搜索树的后序遍历序列

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=9][h

缺乏、安全感/ 2022年03月20日 02:48/ 0 赞/ 125 阅读

相关【剑指Offer】（树）二叉搜索树的后序遍历序列

题目链接：[https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11

╰+攻爆jí腚メ/ 2022年03月16日 01:06/ 0 赞/ 184 阅读

相关二叉搜索树的后序遍历序列

时间限制：1秒空间限制：32768K 热度指数：332916 算法知识视频讲解题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则

小灰灰/ 2022年03月10日 11:42/ 0 赞/ 132 阅读