二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5] 输出: false
示例 2：
输入: [1,3,2,6,5] 输出: true
提示：
数组长度 <= 1000
解法一：递归
后续遍历的最后一个节点是根节点，而且后续遍历序列中，左右两个子树一定是分开的。因此，可以根据根节点的值，找到左子树和右子树。
[1 3 2 6 5] 根节点为 5，因此 [1 3 2] 一定是左子树，6 一定是右子树。在 [1 3 2] 中，2 是根节点， 1 一定是左子树，3 是右子树。因此这个序列是合理的。
[1 6 3 2 5] 根节点是 5，那么从左到右找第一个大于 5 的数为 6，因此 1 是左子树。[6 3 2] 是右子树。可以看出右子树存在小于根节点的元素，因此不符合要求。
实际写代码的时候，可以递归地检查每个子树，同时把这个子树的最大值和最小值传进入，在递归过程中检查是否符合范围要求。
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
return verify(postorder.begin(), postorder.end(),
numeric_limits<int>::min(), numeric_limits<int>::max());
}
private:
using iterator = vector<int>::iterator;
bool verify(iterator first, iterator last, int lo, int hi){
if(first == last) return true;
--last;
int root = *last;
if(root < lo || root > hi) return false;
if(first == last) return true;
auto it = find_if(first, last, [root](int n){
return n > root;
});
return verify(first, it, lo, root) && verify(it, last, root, hi);
}
};
解法二：单调栈、
一个树的右孩子、右孩子的右孩子……，一定构成一个递增序列。可以使用一个单调递增栈来记录这些节点。
使用单调栈记录和更新余下元素的上界，然后检查是否存在不符合上界约束的元素。
举个例子：
对于序列 [1 3 2 6 5] 从后向前遍历 ，将其加入递增单调栈中。
+----------
| 5 6
+----------
当处理到 2 的时候，发现它小于栈顶元素，这说明 2 是栈中某个节点的左孩子，此时就不断出栈，维护栈的单调性。在出栈的时候需要记录下最近出栈的元素，因为该元素就是余下元素的上界。在后续遍历时，要检查各个元素是否小于该上界。
继续处理，6 和 5 都被出栈，此时上界为 5。接着 2 和 3 入栈。
+----------
| 2 3
+----------
当遇到 1 的时候，再次出栈，入栈。最终处理完了整个序列，发现没有不符合上界约束的。因此，该序列是合法的。
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
stack<int> stk;
int prev = numeric_limits<int>::max();
for(auto it=postorder.rbegin();it!=postorder.rend();it++){
if(*it >= prev){
return false;
}
while(!stk.empty() && *it < stk.top()){
prev = stk.top();
stk.pop();
}
stk.push(*it);
}
return true;
}
};