二叉搜索树的后续遍历序列（Python and C++版本）

题目：

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

参考以下这颗二叉搜索树：

5
/
2 6
/
1 3
示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof

思路：

　　首先根据二叉搜索树的特点，数组的最后一个值肯定是根节点，数组中小于该值的属于左子树，大于该值的属于右子树。如果数组中的其他值都大于根节点，则说明根节点只有右子树，没有左子树。

　　当确定完根节点后，需要根据数组元素与根节点的大小关系，确定左子树的元素索引范围和右子树的元素索引范围。当确定了左子树的元素索引之后，若发现数组后面仍有小于根节点的元素，则序列不合理。

　　根据大小关系确定子树是否合理的过程需要递归执行下去，每次递归时，注意子数组的边界，尤其是右子树的边界，不能将父节点包含进去。

Python解法：

 1 class Solution:
 2     def verifyPostorder(self, postorder: List[int]) -> bool:
 3         lenList = len(postorder)
 4         if lenList == 0:
 5             return True
 6 
 7         root = postorder[-1]  # 最后一个值为根节点
 8         leftIndex = 0
 9         for leftIndex in range(lenList):  # 找到左子树的索引范围
10             if postorder[leftIndex] > root:
11                 break
12         rightIndex = leftIndex
13         for rightIndex in range(leftIndex, lenList):  # 判断右子树中是否有不合理的节点
14             if postorder[rightIndex] < root:
15                 return False
16 
17         leftTree = True  # 假设左子树没有问题
18         if leftIndex > 0:  # 递归判断左子树
19             leftTree = self.verifyPostorder(postorder[:leftIndex])
20         rightTree = True  # 假设右子树没有问题
21         if leftIndex < lenList - 1:  # 递归判断右子树
22             rightTree = self.verifyPostorder(postorder[leftIndex:-1])  # 注意排除根节点
23 
24         return leftTree and rightTree  # 如果左右子树都没有问题，则序列没有问题

C++解法：

 1 struct TreeNode {
 2     int val;
 3     TreeNode *left;
 4     TreeNode *right;
 5     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 6 };
 7 
 8 class Solution {
 9 public:
10     bool verifyPostorder(vector<int>& postorder) {
11         int lenVect = postorder.size();
12         if (lenVect == 0)
13             return true;
14 
15         int rootVal = postorder[lenVect - 1];  // 找到根节点
16         int leftIndex = 0;
17         for (; leftIndex < lenVect; leftIndex++)
18             if (postorder[leftIndex] > rootVal)  // 找到左子树的索引范围
19                 break;
20         int rightIndex = leftIndex;
21         for (; rightIndex < lenVect; rightIndex++)
22             if (postorder[rightIndex] < rootVal)  // 判断右子树中是否有不合理的节点
23                 return false;
24 
25         bool leftTree = true;  // 假设左子树没有问题
26         if (leftIndex > 0) {  // 递归判断左子树
27             vector<int> leftElem;  // 左子树元素
28             leftElem.assign(postorder.begin(), postorder.begin() + leftIndex - 1);
29             leftTree = verifyPostorder(leftElem);
30         }
31         bool rightTree = true;  // 假设右子树没有问题
32         if (leftIndex < lenVect - 1) {  // 递归判断右子树,要注意排除根节点
33             vector<int> rightElem;  // 左子树元素
34             rightElem.assign(postorder.begin() + leftIndex, postorder.end() - 1);
35             rightTree = verifyPostorder(rightElem);
36         }
37 
38         return (leftTree && rightTree);
39     }
40 };