题目描述 牛客网

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

题目解读

• 剑指Offer 180

代码

• 第二轮代码：

class Solution {
public:
    bool core(vector<int> &sequence, int left, int right){

        int flag = left;
        bool rchild = false;  // 判断是否有右子树,默认没有右子树
        // 界限处理，left==right表明就一个节点，不管是左树还是右树都符合条件
        if(left >= right){
            return true;
        }
        // sequence[right]是根节点，找到根节点的左子树
        for(int i = left; i < right; i ++){
            if(sequence[i] > sequence[right]){
                flag = i;　// 使 flag 左边的是左子树
                rchild = true;　// 进入if证明存在右子树
                break;
            }
        }
         // 进入此表明此树没有右子树，根本没有进入上一个for里面的if
        if(rchild == false){
            
        }
        else{  // 此树有右子树
            for(int i = flag; i < right; i ++){
                if(sequence[i] < sequence[right]){
                    return false;
                }
            }
        }
        // 递归判断左子树、右子树是不是一颗二叉搜索树
        return core(sequence, left, flag-1) && core(sequence, flag, right-1);
    }

    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0){
            return false;
        }
        return core(sequence, 0, sequence.size() - 1);
    }
};

• 第一轮代码：第二轮看的我好费解啊，仔细看了好几遍，直接看第二轮代码吧，清晰易懂

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool core(vector<int> &sequence, int left, int right){

        int flag = left;

        if(left >= right){
            return true;
        }

        for(int i = left; i < right; i ++){
            if(sequence[i] > sequence[right]){
                flag = i;
                break;
            }
        }

        if(left == flag && sequence[left] < sequence[right]){

        }
        else{
            for(int i = flag; i < right; i ++){
                if(sequence[i] < sequence[right]){
                    return false;
                }
            }
        }
        
        return core(sequence, left, flag-1) && core(sequence, flag, right-1);
    }

    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0){
            return false;
        }

        return core(sequence, 0, sequence.size() - 1);
    }
};

int main(){
    Solution ss;
    vector<int> sequence;
    // int a[7] = {5, 7, 6, 9, 11, 10, 8};
    int a[7] = {4, 6, 7, 5};
    for(int i=0; i < 4; i++){
        sequence.push_back(a[i]);
    }
    cout<<ss.VerifySquenceOfBST(sequence)<<endl;
}

总结展望

• 需要多加思考

扩展题目

• 输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历结果。这和本题的后序遍历很类似，只是在前序遍历得到的序列中，第一个数字是根节点的值