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

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

http://www.nowcoder.com/questionTerminal/a861533d45854474ac791d90e447bafd

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

这道题的解题突破点就在于二叉树的后序遍历数组有着什么的特点?

特点:遍历的时候,如果遇到比最后一个元素大的节点,就说明它的前面都比最后一个元素小,该元素后面的所有值都必须大于最后一个值,这两个条件必须都要满足。否则就说明该序列不是二叉树后序遍历。
例子: 2 4 3 6 8 7 5 这是一个正确的后序遍历
这个例子的特点就是:最后一个元素是 5 ,首先遍历数组,当遍历到6的时候,6前面的值都小于5,如果在6后面的值有一个小于5就不是后序遍历,所以一旦在遍历的时候遇到比最后一个元素的值索引,那么之后的所有元素都必须大于5,否则就不是后序遍历序列。

    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0){
            return false;
        }
        int sum = sequence.size()-1;
        int count = 0;
        while(sum){
            while(sequence[count] < sequence[sum]){
                ++count;
            }
            while(sequence[count] > sequence[sum]){
                ++count;
            }
            if(count < sum){
                return false;
            }
            --sum;
            count = 0;
        }
        return true;
    }
全部评论
有问题,我觉得数据可能太小,让你恰巧AC
3 回复 分享
发布于 2019-11-30 20:45
但你的思路部分正确,你需要递归来处理这个情况
1 回复 分享
发布于 2019-11-30 20:48
哈哈哈哈 nlogn的题硬生生被你写成了n^2的
1 回复 分享
发布于 2020-03-17 10:19
老哥,牛逼!
点赞 回复 分享
发布于 2019-10-03 08:45
二叉树好像不是根据元素的大小来的吧
点赞 回复 分享
发布于 2019-10-17 22:00
对 count为什么不需要约束?
点赞 回复 分享
发布于 2020-04-04 23:30
牛逼,我就写不出这种代码,可以加个栈优化成nlogn
点赞 回复 分享
发布于 2020-05-10 17:58
应该对每个子树都执行这个操作检测一遍才可以
点赞 回复 分享
发布于 2020-07-13 12:29
--sum的操作不明白,应该是递归去解决吧,思想对着
点赞 回复 分享
发布于 2020-07-28 21:52
思路不错,但是时间复杂度有点大呀
点赞 回复 分享
发布于 2020-08-05 19:25
仔细想了想,思路是正确的,不过对额外的节点进行了判断,在去掉根后,对右子树的节点判断时加上了左子树的节点,虽然结果正确,但增大了复杂度。
点赞 回复 分享
发布于 2020-08-17 09:12
这个思路错误的吧
点赞 回复 分享
发布于 2020-10-22 17:03
你这个是错的,思路对,但是你找到分割点以后需要递归处理,而不是一遍就判断完了。很奇怪你为啥不举个反例,就拿你的例子来说,随便找个子树调换一下位置就不成立:[2,3,4,6,8,7,5],这是一个后续遍历,但是这不是一个二叉搜索树。
1 回复 分享
发布于 2021-08-14 13:15
你把充分条件当成必要条件了,逻辑不严谨,举个反例就gg了。
点赞 回复 分享
发布于 2021-10-15 09:50

相关推荐

MomonKa:我拿Java简历投了pdd前端也给我简历过筛了
点赞 评论 收藏
分享
评论
35
6
分享

创作者周榜

更多
牛客网
牛客企业服务