AcWing 46. 二叉搜索树的后序遍历序列

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 46. 二叉搜索树的后序遍历序列原题链接简单

作者：

邓泽军 , 2019-03-11 20:48:45 , 所有人可见 , 阅读 7495

37

11

题目描述

视频里面最后一句是不是有问题呀，为啥还ac了，dfs(k, r-1).

样例

class Solution {
public: 
    vector<int> seq;

    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        return dfs(0, seq.size() - 1);
    }
    bool dfs(int l, int r) {
        if (l >= r)  return true;
        int root = seq[r];
        int k = l;
        while(k < r && seq[k] < root) k ++;
        for(int i = k; i < r; i ++) {
            if (seq[i] < root)
                return false;
        }
        return dfs(l, k - 1) && dfs(k, r-1);
    }
};

10 评论

jieHeEternity 2022-02-13 10:00

//什么是二叉搜索树
/
它或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
/

class Solution {
public:
bool dfs(int st,int idx,vector[HTML_REMOVED]seq)
{

    // cout<<st<<" "<<idx<<endl;
    if(idx<=st)return true;
    int rot = seq[idx];
    int j=idx;

    while(j>st&&(seq[j]>seq[idx]||j==idx))j--; 
    cout<<j<<endl;
    for(int k=j;k>=st;k--)
    {
        if(seq[k]>=seq[idx])return false;
    }

    return dfs(j+1,idx-1,seq)&&dfs(st,j,seq);



    return true;


}
bool verifySequenceOfBST(vector<int> seq) {
    if(seq.empty())return true;

    int n = seq.size();

    return dfs(0,n-1,seq);
}

};
问下，这道题我的思路是从后往前写的dfs，你看下，思路我调了感觉没啥问题
在2 1 3 这组数据上可以测出bug
大佬帮忙看下是不是只能从左往由写，不能从右往左写。