二叉树中后序序列求先序序列c++

在二叉树中，给定后序遍历（Postorder Traversal）的节点序列，重建其对应的先序遍历（Preorder Traversal）序列是一个常见的编程问题。这里我们可以借助栈的数据结构来解决。下面是C++的一个解决方案：

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

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 后序遍历序列
vector<int> postOrder;

// 先序遍历辅助函数
void preOrderHelper(TreeNode* root) {
    if (root == nullptr)
        return;

    // 将当前节点压入栈
    stack<TreeNode*> s;
    s.push(root);

    // 当栈非空时
    while (!s.empty()) {
        // 弹出栈顶元素并访问（即先序的前半部分）
        TreeNode* node = s.top();
        cout << node->val << " "; // 输出节点值
        s.pop();

        // 如果左孩子存在，先访问左孩子（后序遍历的特点）
        if (node->left != nullptr)
            s.push(node->left);
        
        // 如果右孩子存在，先访问右孩子（后序遍历的特点）
        if (node->right != nullptr)
            s.push(node->right);
    }
}

// 主函数
void getPreOrderFromPostOrder(vector<int>& postOrder) {
    TreeNode* root = new TreeNode(postOrder.back()); // 使用最后一个元素创建根节点
    postOrder.pop_back(); // 移除后序遍历中的最后一个元素

    // 根据后序遍历的逆过程重建二叉树，然后进行先序遍历
    for (int i = postOrder.size() - 1; i >= 0; i--) {
        TreeNode* node = new TreeNode(postOrder[i]);
        if (i > 0 && postOrder[i-1] > postOrder[i]) { // 找到右孩子
            node->right = &postOrder[i-1];
            postOrder[i-1].left = node;
        } else { // 找到左孩子
            node->left = &postOrder[i];
            postOrder[i].right = node;
        }
    }

    preOrderHelper(root); // 调用先序遍历辅助函数
}

int main() {
    vector<int> postOrder = {4, 5, 2, 8, 1, 6, 3, 7}; // 示例后序遍历序列
    getPreOrderFromPostOrder(postOrder);
    return 0;
}

这个程序首先创建一个二叉搜索树，其中根节点是后序遍历序列中的最后一个元素，然后根据后序遍历特点逆向重建树，并进行先序遍历。