二叉树遍历序列转换详解：中序+后序递归重建先序（C++实现）

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）。

输入输出示例

样例1：

输入
BADC
BDCA
输出
ABCD

一、核心思路与递归方法

解决此类问题的关键在于理解二叉树的遍历特性并掌握递归重建的方法。

1. 利用后序与中序序列重建树形结构

重建过程遵循以下三步逻辑：

• 后序遍历特性：序列遵循 左子树 → 右子树 → 根节点 的顺序。因此，后序序列的最后一个元素一定是整棵树的根节点（在处理子树序列时，该规律依然成立）。
• 中序遍历特性：序列遵循 左子树 → 根节点 → 右子树 的顺序。根据根节点在中序序列中的位置，可以明确划分出左子树和右子树的序列区间。
• 递归拆解：以后序序列的根节点为基准，找到它在中序序列中的位置。以此位置为界，将中序序列划分为左、右子树。然后，根据划分出的子树区间长度，在后序序列中定位子树的根节点，递归处理左、右子树，直到子树为空。

下图清晰地展示了根据中序和后序序列计算左右子树下标范围的方法：

根据上述思路，我们可以实现递归函数的核心骨架：

// 递归拆解二叉树中序序列
void dfs(int k, int l, int r) { // k：后序中根节点的位置；l/r：中序序列的当前处理范围
    if(l > r) return ; // 区间处理完毕
    // 在中序找到当前根节点位置后再递归处理中序的左右子树区间
    for(int i=l; i<=r; i++){
        if(sm[i]==s[k]){ // 找到当前根节点位置
            int lenl=i-l, lenr=r-i; // 根据中序下标计算左右子树大小
            dfs(k-1-lenr, l, i-1); // 递归处理左子树
            dfs(k-1, i+1, r);      // 递归处理右子树
        }
    }
}

2. 在先序位置输出根节点

我们的目标是得到先序遍历序列，其顺序是：根节点 → 左子树 → 右子树。因此，只需在递归处理左、右子树之前，输出当前找到的根节点即可。

对上面的核心代码稍作修改，加入输出语句：

if(sm[i]==s[k]){ // 找到当前根节点位置
    int lenl=i-l, lenr=r-i; // 根据中序下标计算左右子树大小
    cout << s[k];           // 输出根节点 (先序位置)
    dfs(k-1-lenr, l, i-1);  // 递归处理左子树
    dfs(k-1, i+1, r);       // 递归处理右子树
}

3. 主函数调用与初始化

最后，在main函数中进行必要的初始化并启动整个递归过程。特别注意，首次调用时传入的是整个序列的范围。

string sm, s; // 分别存储中序(inorder)和后序(postorder)序列
int n; // 序列长度
// ... 此处省略递归函数dfs的定义

int main(){
    cin >> sm >> s;          // 读入中序和后序字符串
    n = sm.size();           // 计算序列长度
    dfs(n-1, 0, n-1);        // 从后序最后一个元素（整树根）开始，处理整个中序序列[0, n-1]
    return 0;
}

二、举一反三：如何改为中序+先序推导后序？

理解了中序+后序推导先序的原理，将其调整为中序+先序推导后序就非常简单了，只需调整两个地方。

1. 调整递归调用时“根节点位置”参数

在先序遍历中，序列顺序是 根节点 → 左子树 → 右子树。因此，当我们在中序序列中找到根节点位置 i 后：

• 左子树的根节点在先序序列中的位置是 k+1（紧跟着当前根节点）。
• 右子树的根节点在先序序列中的位置是 k+1+lenl（跳过左子树的所有节点）。

// 参数k：当前子树根节点在先序中的位置
dfs(k+1, l, i-1);        // 递归处理左子树
dfs(k+1+lenl, i+1, r);   // 递归处理右子树

2. 在后序位置输出根节点

后序遍历的顺序是 左子树 → 右子树 → 根节点。因此，我们需要在递归处理完左、右子树之后，再输出根节点。

if(sm[i]==s[k]){ // 找到当前根节点位置
    int lenl = i - l;
    dfs(k+1, l, i-1);        // 递归处理左子树
    dfs(k+1+lenl, i+1, r);   // 递归处理右子树
    cout << s[k];           // 输出根节点 (后序位置)
}

3. 主函数调用的调整

由于整个二叉树的根节点在先序序列的第一个位置，所以初始调用时 k 应为 0。

int main(){
    cin >> sm >> s; // 此时s为先序序列
    n = sm.size();
    dfs(0, 0, n-1); // 从先序第一个元素（整树根）开始处理
    return 0;
}

通过对核心递归逻辑的微调，我们就能在不同的遍历序列之间进行转换，这充分体现了对二叉树遍历本质理解的重要性。如果你在实践中遇到其他有趣的算法问题，欢迎到云栈社区与大家一起交流探讨。