# 面试题33
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
```
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
```
## 提示：
* 数组长度 <= 1000
## Solutions
1. **mono stack**
2. reference:
3. This solution is based on the fact that postorder traversal is the opposite of preorder traversal. ie: preorder(Similar): `root right left` -> postorder: `left right root`
4. Maintain a monotonically increasing stack which records the path when traversing the right subtree(Mono increasing).
5. This solution works only if there are no duplicate elements in the given sequence.
```cpp
class Solution {
public:
bool verifyPostorder(vector& postorder) {
stack s;
int cur = postorder.size() - 1;
int rootval = INT_MAX;
for (int cur = postorder.size() - 1; cur >= 0; cur--) {
if (postorder[cur] > rootval)
return false;
// find the root node
while (!s.empty() && s.top() > postorder[cur]) {
rootval = s.top();
s.pop();
}
s.push(postorder[cur]);
}
return true;
}
};
```
1. **recursion**
2. In each recursive call, find the first element of the right subtree(val > root->val).
```cpp
class Solution {
public:
bool valid(vector & postorder, int lo, int hi) {
if (lo >= hi)
return true;
// the root val is the last element
int rootval = postorder[hi];
int mid = lo;
while (postorder[mid] < rootval && mid < hi)
mid++;
// check if the right tree is valid
for (int r = mid; r < hi; r++)
if (postorder[r] < rootval)
return false;
return valid(postorder, lo, mid - 1) && valid(postorder, mid, hi - 1);
}
bool verifyPostorder(vector& postorder) {
return valid(postorder, 0, postorder.size() - 1);
}
};
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://zhongquan789.gitbook.io/leetcode/lcof/mian-shi-ti-33.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.