剑指Offer-二叉搜索树的后序遍历序列

发表于 | 分类于

题目描述

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

思路分析

这道题又是没有思路，只能看看提示。自己也是够蠢，居然忘记了后序遍历根的特性！！！BST(Binary-Search-Tree)的后序序列的合法序列是，对于一个序列S，最后一个元素是x(也就是根)，如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。使用递归即可解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0) return false;
        if(sequence.size()==1) return true;   
        return verifybst(sequence, 0, sequence.size()-1);//相信自己的第一直觉
    }
    
    bool verifybst(vector<int> bst, int begin, int end){
        int i = begin;
        while(bst[i] < bst[end]) // 左半部分
            i++;
        int j = i;
        for(; j<end; j++) // 右半部分
            if(bst[j] < bst[end]) 
                return false;
        if(j == end) return true; //！这里是教训
        return verifybst(bst, begin, i-1) & verifybst(bst, i, end);
    }
};

记住，不一定只能使用一个函数，在必要的时候可能定义其他函数。另外，必须要有结束的条件，因此必定有return false和return true两种情况，吸取教训！