给定二叉搜索树的前序遍历，求它的后序遍历

问题描述:

输入第一行一个正整数 n (n <= 20)，表示二叉搜索树节点个数。 接下来一行有 n 个数字，表示二叉搜索树的前序遍历序列。 输出一行 n 个数字，表示二叉搜索树的后序遍历序列。

样例输入:

5 3 1 2 4 5

样例输出:

2 1 5 4 3

题目分析:

这道题目可以利用二叉搜索树的性质：左子树的值都比根节点的值小，右子树的值都比根节点的值大。根据前序遍历的特点，第一个节点是根节点，接下来是左子树的节点，最后是右子树的节点。因此，可以根据这个特点，递归地构建出整棵树，然后进行后续遍历即可。

具体实现可以利用两个指针 i 和 j，i 指向当前节点在前序遍历中的位置，j 指向当前子树在前序遍历中的末尾位置。每次在前序遍历中找到第一个大于根节点值的位置，将其作为左右子树的分隔点，然后用同样的方式递归构建左右子树即可。

代码实现:

#include <iostream>
using namespace std;

const int MAXN = 25;
int preOrder[MAXN]; // 前序遍历序列
int postOrder[MAXN]; // 后序遍历序列

void buildTree(int i, int j, int k, int l) { // i 为当前子树在前序遍历中的起始位置，j 为末尾位置，k 为当前子树在后序遍历中的起始位置，l 为末尾位置
    if (i > j) return; // 当前子树为空，直接返回
    postOrder[l] = preOrder[i]; // 根节点为前序遍历中的第一个节点，也是后序遍历中的最后一个节点
    int p = i + 1; // p 指向左子树的第一个节点
    while (p <= j && preOrder[p] < preOrder[i]) p++; // 找到左右子树的分隔点
    buildTree(i + 1, p - 1, k, k + p - i - 2); // 递归构建左子树
    buildTree(p, j, k + p - i - 1, l - 1); // 递归构建右子树
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> preOrder[i];
    }
    buildTree(0, n - 1, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << postOrder[i] << ' '; 
    }
    cout << endl;
    return 0;
}

代码解释:

1. buildTree(int i, int j, int k, int l) 函数用于递归构建二叉搜索树。
2. i 和 j 分别表示当前子树在前序遍历中的起始位置和末尾位置。
3. k 和 l 分别表示当前子树在后序遍历中的起始位置和末尾位置。
4. 递归终止条件为 i > j，表示当前子树为空。
5. 找到当前子树的根节点 preOrder[i]，并将它放到后序遍历序列的末尾位置 postOrder[l]。
6. 利用 while 循环找到左右子树的分隔点 p。
7. 递归调用 buildTree 函数分别构建左右子树。

总结:

通过上述代码实现，我们能够根据给定的二叉搜索树的前序遍历序列，利用递归算法构建整棵树并得到其后序遍历序列。该算法利用了二叉搜索树的性质和前序遍历的特点，具有简洁高效的优势。