剑指offer-23-二叉搜索树的后序遍历序列

二叉搜索树的后序遍历序列_牛客网

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

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

** 第一眼看到题目似乎有一些陌生,但是把二叉搜索树画出来并回忆其特性之后思路就渐渐形成了,并且看了一下其他小伙伴的思路,基本上是一致的。在编写的过程中,唯一不足的是忽略了java中数组可以为null,也可以为[],这个和c、c++语言空即null是不同的,需要额外注意一下**

public class Solution {

    public boolean helpVerify(int [] sequence, int start, int root){
        if(start >= root)return true;
        int key = sequence[root

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

小白刷剑指offer 文章被收录于专栏

跟着小白一起刷剑指offer,通过讨论加深印象吧~ 没有人不学习就能够掌握知识,知识就是需要学习的~

全部评论
确实,返回类型为ArrayList之类的,返回值设为null会报NullPointerException
点赞
送花
回复
分享
发布于 2019-11-14 20:58
如果根节点为1,左孩子为2,右孩子为3,这样也是返回true,但其实这并不是一棵二叉搜索树,代码有问题哦。
1
送花
回复
分享
发布于 2020-04-14 11:20
滴滴
校招火热招聘中
官网直投
如果只有左子树的例如[4,5,6,7]就会报错,应该返回True结果返回false
1
送花
回复
分享
发布于 2020-04-24 09:10
大佬,if(start >= root)return true;这句base case为什么需要>= ,我理解的是只要递归里只剩一个数了判断start==root就可以返回true了,但是改成if(start == root)return true;会出错,改成if(start > root)return true;也能通过
1
送花
回复
分享
发布于 2020-07-05 17:38
if(start >= root)return true;这句base case为什么需要>=,为什么等于号就不可以
1
送花
回复
分享
发布于 2020-08-03 17:09
6785
点赞
送花
回复
分享
发布于 2019-10-01 14:11
虽然你这颗树不满足,但满足其他:1为根,2,3为右子树。题目是只要有树能满足即可
点赞
送花
回复
分享
发布于 2020-04-14 12:10
了解,是在下审题不清,见谅
点赞
送花
回复
分享
发布于 2020-04-14 16:09
if(start >= root)return true; 这句代码真的不太懂,似乎没有意义?
点赞
送花
回复
分享
发布于 2020-04-27 17:42
return helpVerify(sequence, start, i-1) && helpVerify(sequence, i, root-1); 这句后半部分有什么用呢,感觉没用啊
点赞
送花
回复
分享
发布于 2020-05-24 16:11
代码很优雅,可读性很强,太厉害了
点赞
送花
回复
分享
发布于 2020-08-02 17:38
该实现时间复杂度为nlogn,判断右子树时间复杂度还有优化空间,可嵌入至递归过程,时间复杂度logn
点赞
送花
回复
分享
发布于 2021-04-07 12:08
点赞
送花
回复
分享
发布于 2021-10-20 21:34

相关推荐

77 6 评论
分享
牛客网
牛客企业服务