题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805440976633856
题目大意：给出一串序列，这串序列有可能是一棵二叉搜索树（或一棵镜像二叉搜索树）的先序遍历。如果是的话，给出这棵BST的后序遍历。
思路：一开始奇怪只有先序遍历如何得到一棵二叉搜索树。但因为是先序遍历，序列的结构一定是（parent, left_subtree, right_subtree）。左子树的元素都小于parent，右子树的元素都大于等于parent，那么重点就是找出左右子树的分界点。
找分界点，很自然想到是用递归。那有什么要传入这个递归函数呢，parent的位置是一定要传的。但仅仅如此，还不好确定要搜索的范围。看了柳神的解答后，发现：此外这一层的尾部位置也要传入。
完整代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;vector<int> arr(1);
vector<int> post(1);
bool isMirror;void getPost(int head, int rear) {
if (head > rear)return;int parent_val = arr[head];int right_head = head + 1, left_rear = rear;if (!isMirror) {
while (right_head <= rear && arr[right_head] < parent_val)right_head++;while (left_rear > head && arr[left_rear] >= parent_val)left_rear--;}else {
while (right_head <= rear && arr[right_head] >= parent_val)right_head++;while (left_rear > head && arr[left_rear] < parent_val)left_rear--;}if (right_head - left_rear != 1)return;getPost(head+1, left_rear);getPost(right_head, rear);post.push_back(arr[head]);
}int main() {
int N;cin >> N;arr.resize(N);post.clear();for (int i = 0; i < N; i++)cin >> arr[i];isMirror = false;getPost(0, N-1);if (post.size() != N) {
isMirror = true;post.clear();getPost(0, N - 1);}if (post.size() == N) {
cout << "YES" << endl;for (int i = 0; i < N; i++) {
if (i)cout << " " << post[i];elsecout << post[i];}}elsecout << "NO";return 0;
}
重点是getPost()这个递归函数，它做的事情是：找到分界点，判断是否满足二叉搜索树，如果满足，则对左右子树递归，并把parent元素push进post数组中。注意顺序，先递归再push自己的，这样才能保证post数组中的顺序是后序遍历。
if (right_head - left_rear != 1)return;getPost(head+1, left_rear);getPost(right_head, rear);post.push_back(arr[head]);
可以看到条件判断，它发现这一层不满足二叉搜索树的条件时就return了，那么post数组中元素个数就会少，在main函数中发现了就转为另一种BST的判断（镜像）。最后输出结果即可。
if (post.size() != N) {
isMirror = true;post.clear();getPost(0, N - 1);}if (post.size() == N) {
cout << "YES" << endl;for (int i = 0; i < N; i++) {
if (i)cout << " " << post[i];elsecout << post[i];}}elsecout << "NO";
感想：起初大致思路和柳神是一样的，单具体在实现递归时，要传入哪些元素却没弄清除。整个程序重点还是在递归，并且在递归时巧妙地完成了后序遍历的记录，这点也是很重要的（我一开始只想到用递归来判断，得到YES/NO的结果，后序遍历却没想到在这里一起实现，还以为要自己构造BST了…）