M22275: 二叉搜索树的遍历

http://cs101.openjudge.cn/practice/22275/

思路：左子树所有节点值小于根节点，右子树所有节点值大于根节点。结合前序遍历，通过递归划分左右子树，最终得到后序遍历

#include <iostream>
#include <vector>
using namespace std;

vector<int> getPostorder(vector<int>& pre, int l, int r) {
    if (l > r) return {}; 
    int root = pre[l];   
    int mid = l + 1;
    while (mid <= r && pre[mid] < root) {
        mid++;
    }
 
    vector<int> left = getPostorder(pre, l + 1, mid - 1);
    vector<int> right = getPostorder(pre, mid, r);
    vector<int> res;
    res.insert(res.end(), left.begin(), left.end());
    res.insert(res.end(), right.begin(), right.end());
    res.push_back(root);
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> pre(n);
    for (int i = 0; i < n; ++i) {
        cin >> pre[i];
    }
    vector<int> post = getPostorder(pre, 0, n - 1);
    for (size_t i = 0; i < post.size(); ++i) {
        if (i > 0) cout << " ";
        cout << post[i];
    }
    cout << endl;
    return 0;
}