首页 > 试题广场 >

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

[编程题]二叉搜索树的后序遍历序列

热度指数：876042 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

数据范围：节点数量 $0 \le n \le 1000$ ，节点上的值满足 $1 \le val \le 10^{5}$ ，保证节点上的值各不相同
要求：空间复杂度 $O(n)$ ，时间时间复杂度 $O(n^2)$

提示：

1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。

2.该题我们约定空树不是二叉搜索树

3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历

4.参考下面的二叉搜索树，示例 1

示例1

输入

[1,3,2]

输出

true

说明

是上图的后序遍历 ，返回true

示例2

输入

[3,1,2]

输出

false

说明

不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列 ，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false

示例3

输入

[5,7,6,9,11,10,8]

输出

true

算法知识视频讲解

幸福的火龙果在干饭

发表于 2021-06-29 22:04:02

精华题解一、题目描述 JZ23 二叉搜索树的后序遍历序列题目大意：输入一个序列, 判断它是不是某二叉搜索树的后序遍历结果注意审题：假设输入序列的任意两个数字都互不相同且空树不是二叉搜索树二、算法1（分治）解题思路二叉树的后序遍历顺序是：左子树 -> 右子树 -> 根节点因此序列的最后一展开全文

不是江小白

发表于 2021-07-12 20:38:20

精华题解 1. 常规思路：递归 1.1 两个前提：首先是二叉搜索树（左子树每个节点的值 < 该节点的值 < 右子树每个节点的值）的特点；其次是后序遍历（对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身）的特点。 1.2 图解示例：输入： [4,8,6 展开全文

牛客500979850号

发表于 2021-07-17 22:42:18

精华题解方法一：递归较自然的思路，遵循后序遍历的规则:左子树->右子树->根节点。因此当前序列的最后一个值即为根节点，且左子树<根节点<右子树。每次遍历当前序列，根据大小顺序判断是否符合条件，同时得到左右子树序列，并递归调用函数判断子树序列是否符合条件。class Solutio 展开全文

Maokt

发表于 2021-06-22 09:08:04

精华题解解题思路： 1、根据二叉搜索树的后续遍历规律：左子树--右子树--根；序列最后一个元素为根节点，左子树的元素值都小于根节点，右子树的元素值都大于根节点。（1）将数组的元素分为两部分：左子树序列值和右子树序列值，左子树值都小于根节点值，右子树值都大于根节点值（2）分别对左右子树展开全文

leaves0924

发表于 2021-06-21 15:09:34

精华题解题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）示例1输入：[4,8,6,12,16,14,10]返回值：true 题目分析首先，二叉搜索树的特点是根节点展开全文

牛客题解官

发表于 2022-04-25 18:17:24

精华题解题目的主要信息：题目给出我们一个一维数组sequence 该数组需要我们判定数组sequence中的元素是否符合一个二叉搜索树的后序遍历顺序如果该数组sequence可以是一种二叉搜索树的后序遍历顺序，则返回true 如果该数组sequence非二叉搜索树的后序遍历顺序，则返回false 举展开全文

Peterliang

发表于 2021-06-21 20:02:43

精华题解题意分析题意给出一个二叉树的后序遍历的结果，需要我们判断这棵二叉树是否为二叉搜索树。样例解释首先，我们来说明一下本题目的样例样例如上图，看图知道，这个就是一个二叉搜索树。所以返回的是true。但是，我们如何用程序实现这种判断呢？前置知识什么是二叉搜索树，简单来说，就是对于一个二展开全文

凉风起天末

发表于 2019-09-04 02:04:53

从到，比递归效率更高的方法：上限约束法方法一：递归法递归简单易懂容易实现，先来一次遍历以确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。现在让我们来分析一下递归方法的时间复杂度：二叉搜索树不一定是棵平衡二叉树，因此其树形可能长得奇形怪状，最坏的情况下可能退化成一类似链表的结构，此时我们展开全文

一叶浮尘

发表于 2019-08-16 07:40:19

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 ** 第一眼看到题目似乎有一些陌生，但是把二叉搜索树画出来并回忆其特性之后思路就渐渐形成了，并且看了一下其他小伙伴的思路，基本上是一致的。在编写的过程中，唯展开全文

jalr4ever

发表于 2019-08-26 14:18:47

题目输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思路二叉搜索树，举例如下：结合图中分析：一棵 BST ：左孩子 < 根结点 < 右孩子一棵 BST 的左子树或者右子树都是 B 展开全文

程序猿的浪漫

发表于 2019-09-30 22:43:52

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果，如果是则输出Yes,否则输出No；假设输入的数组的任意两个数字都互不相同。这道题的解题突破点就在于二叉树的后序遍历数组有着什么的特点？特点：遍历的时候，如果遇到比最后一个元素大的节点，就说明它的前面都比最后一个元素小，该元素后展开全文

小明同学#

发表于 2019-09-26 20:33:37

import java.util.Arrays; public class Solution { public boolean VerifySquenceOfBST(int []&n 展开全文

开挂了的回宇同桌很有趣

发表于 2021-10-10 11:10:04

import java.util.*; public class Solution { /* 思路：由于题目给出的是二叉搜索树的后续校验。所以，我们应该充分的往二叉搜索树中的性质方面考虑，并且利用它的性质解题性质：对于任何一个根来说，根的左边全部小于根展开全文

遗忘201901051244512

发表于 2020-03-15 00:10:44

一、递归法 1.分析：一次遍历确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。2.代码 bool IsBST(const vector<int>& sequence, const int start, const int end){ if (st 展开全文

墨白tyrant

发表于 2021-11-02 21:17:47

思路：倒序输出的时候是：根→右→左，其中左子节点的值恒小于根和右，于是便有遍历满足条件：①递增时候无任何问题，②递减时候要求必须小于以前所有数。依次为条件，先遍历入栈，再在递减时出栈对比即可。 public class Solution { public boolean VerifySque 展开全文

牛客825789185号

发表于 2021-10-05 19:59:23

class Solution { public: /* 搜索二叉树的后序遍历结果，当前根结点左儿子下标，一定是 * 最后一个小于根节点元素的下，右儿子下标，一定是大于根节点的最后一个元素下标 * 4，8，6，12，16，14，10 子结点查找范围展开全文

常喝水

发表于 2020-02-02 17:04:52

数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大 class Solution: def VerifySquenceOfBST(self, sequence): # write code h 展开全文

问题信息

栈树

难度：

1527条回答 4094收藏 177225浏览

通过挑战的用户

查看代码

cramin

2023-03-09 11:49:48
Elastic...

2023-02-26 22:24:20
牛客74843...

2022-10-16 13:51:53
想成为大佬的小菜鸡

2022-09-16 15:19:39
95年的巨蟹

2022-09-16 11:16:37

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

输入

输出

说明

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题