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

题目描述

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

思路：

一说到 二叉搜索树 一定要想到，左子树的值 < root 结点的值 < 右子树的值

对于二叉树

    8
   / \
  6   10
 / \  / \
5  7 9  11

判断后序遍历（左-右-根） { 5,7,6,9,11,10,8 } 是不是正确？

• 元素 8 一定为 root 结点，从前往后找到第一个比 8 大的元素 a，a 的左侧即为 root 的左子树。这里的 a 就是 9， 也就是说 9 之前的 {5,7,6 } 是左子树
• 然后从 a 开始，往右遍历到 root 结点，判断右子树的值是不是都大于 root 结点的值，若不是，return false。这里的 9 之后 {11,10} 都大于 8 。
• 将 a 的左侧部分 和 右侧部分分别做上两步的递归

C++ 代码

class Solution{
public:
	 bool VerifySquenceOfBST(vector<int> seq) {
        if(seq.empty()) return false; //空的，返回false
        return judge(seq, 0, seq.size() - 1);
    }
    bool judge(vector<int> &seq, int l, int r)
    {
    	int root = seq[r]; 
    	int k = l;
    	if(l >= r) return true;
    	while(k < r && seq[k] < root)
    		k++;
    	for(int i = k; i < r; i++){
    		if(seq[i] < root)
    			return false;
    	}
		return judge(seq, l, k-1) && judge(seq, k, r-1);    
    }
};