一、题目

二、思路

单纯根据后序遍历序列，不阔能确定一棵二叉树，但是事先说明是二叉搜索树BST了，BST树的特点是中序遍历序列，是有序序列，而且根结点val大于左孩子val，小于右孩子val。

而且题目给出后序遍历序列，最后一个节点是根结点，我们就能从头遍历数组，找到第一个比根结点大的节点位置（分界点），在此前面的部分，都是根结点的左子树部分；分界点后面部分理应是右子树部分，所以val也理应该大于根结点。所以基于这点，我们只要判断分界点后的结点值，是否有小于根结点的这种异常情况，则说明不是BST的后序序列。

三、代码

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return dfs(postorder, 0, postorder.size() - 1);
    }   
    bool dfs(vector<int>& postorder, int left, int right){
        //如果数组中只剩下一个元素或没有元素，则肯定满足
        if(left >= right){
            return true;
        }
        int temp = left;
        //找分界点
        while(postorder[temp] < postorder[right]){
            temp++;
        }
        int a = temp;
        //判断分界点后面的结点val，是否还有小于根结点val的
        while(temp < right){
            if(postorder[temp++] < postorder[right]){
                return false;
            }
        }
        return dfs(postorder, left, a - 1) 
               && dfs(postorder, a, right - 1);
    }
};

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/123542627