一、题目
二、思路
单纯根据后序遍历序列，不阔能确定一棵二叉树，但是事先说明是二叉搜索树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); } };
