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

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

题目描述

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

不是很懂, 待解决

大体思路是找数组中比最后一个元素大的第一个元素的位置, 这个元素之后的所有元素要比最后一个元素大, 否则返回false, 解题有递归版和非递归版, 均源自牛客网, 不过原版中把自增都写入while循环中, 貌似有些问题

递归版:

class Solution {
public:
    
    bool isLastOrder(vector<int> sequence, int b, int e) {
        if (b == e) {
            return true;
        }
        int mid = b;
        while(sequence[mid] < sequence[e] && mid < e) 
            mid++;
        int temp = mid;
        while(sequence[temp] > sequence[e] && temp < e)
            temp++;
        if (temp < e){
            return false;
        }
        if(mid == e || mid == b) {
            return isLastOrder(sequence, b, e - 1);
        }
        else {
            return isLastOrder(sequence, b, mid - 1) && isLastOrder(sequence, mid, e - 1);
        }
    }
    
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) {
            return false;
        }
        
        return isLastOrder(sequence, 0, sequence.size() - 1);
    }
};

非递归版:

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(0 == sequence.size()) {
            return false;
        }
        
        int i = sequence.size();
        int j = 0;
        while(--i) {
            while((sequence[j] < sequence[i]) && j < i)    j++;
            while((sequence[j] > sequence[i]) && j < i)    j++;
            if (j != i)    return false;
            else {
                j = 0;
            }
        }
        
        return true;
    }
};