NO23、二叉搜索树的后序遍历序列(好题,值得再看一遍)

23、二叉搜索树的后序遍历序列 好题,值得再看一遍

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

[4,8,6,12,16,14,10]

返回值

true
1、递归写法,树主要的做法就是递归
bool VerifySquenceOfBST(vector<int> sequence) {
    if (sequence.empty())  return false;
    if (sequence.size() == 1) return true;
    return VerifySquenceOfBSTCore(sequence, 0, sequence.size()-1);
}

bool VerifySquenceOfBSTCore(vector<int>& sequence, int start, int end) {
    if (start >= end) return true;
    int low = start;
    while (low < end && sequence[low] < sequence[end])  ++low;

    for (int i = low; i < end; ++i) {
        if (sequence[i] <= sequence[end]) return false;
    }

    return  VerifySquenceOfBSTCore(seq

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

带你刷完67道剑指offer 文章被收录于专栏

- 本专栏汇集了67道剑指offer的一些精妙解法,不少题有5-6种解法之多,有些题目二刷三刷的解法也不一样。 - 本专栏帮助我拿到6个互联网大厂offer,最终圆梦字节跳动公司。

全部评论
这道题的题目描述有笔误,粘贴了上一题的。
点赞 回复 分享
发布于 2021-01-24 11:08

相关推荐

06-28 22:48
已编辑
广东金融学院 Java
小浪_Coding:学院本+这俩项目不是buff叠满了嘛
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务