二叉树深度计算与先序序列重构算法解析

已知一棵二叉树的中序遍历序列和后序遍历序列，求其先序遍历序列。

核心思路

后序遍历的最后一个元素一定是当前子树的根节点。找到该根节点在中序遍历中的位置，即可将中序序列划分为左子树和右子树部分。

1. 确定根节点（后序序列末尾）。
2. 在中序序列中找到根节点位置 p。
3. 递归处理左子树（中序 [l1, p-1]，后序对应区间）。
4. 递归处理右子树（中序 [p+1, r1]，后序对应区间）。
5. 输出顺序为：根 -> 左 -> 右。

代码实现

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

string a, b; // a 为中序，b 为后序

void dfs(int l1, int r1, int l2, int r2) {
    // 递归出口：区间无效
    if (r1 < l1) return;

    // 确立根节点并输出（先序特性）
    cout << b[r2];

    // 寻找中序序列中的根节点位置
    int p = l1;
    while (a[p] != b[r2]) p++;

    // 递归处理左右子树
    // 左子树：中序 [l1, p-1]，后序长度相同
    dfs(l1, p - 1, l2, l2 + p - l1 - 1);
    // 右子树：中序 [p+1, r1]，后序剩余部分
    dfs(p + 1, r1, l2 + p - l1, r2 - 1);
}

int main() {
    cin >> a >> b;
    dfs(0, a.size() - 1, 0, b.size() - 1);
    return 0;
}

总结

这两道题是树形结构递归应用的典型代表。第一题考察对树高定义的理解，第二题考察序列特征与递归划分的结合。掌握这类问题的关键在于找准递归的终止条件和状态转移方程。在实际刷题中，建议多画图辅助理解区间变化，避免边界错误。