二叉树算法实战：深度计算与先序排列求解

注意： 实际运行时需注意输入数据的合法性，确保没有环且所有节点都能从根节点访问到。数组大小需根据题目约束预留足够空间。

二、求先序排列

1. 题目描述

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

2. 算法思路

这道题的核心在于利用后序遍历的特性确定根节点。后序遍历的顺序是'左 - 右 - 根'，因此后序序列的最后一个字符一定是当前子树的根节点。

找到根节点后，在中序遍历序列中找到该根节点的位置，即可将中序序列划分为'左子树部分'和'右子树部分'。随后，根据左右子树的长度，在后序序列中也能对应划分出左右子树的后序区间。通过递归地重复这一过程，即可还原整棵树的先序结构。

关键在于如何准确计算区间的边界索引，这是递归最容易出错的地方。

3. 代码实现

#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]
    // 左子树在后序中的范围：[l2, l2 + (p - 1 - l1)]
    dfs(l1, p - 1, l2, l2 + p - l1 - 1);

    // 递归处理右子树
    // 右子树在中序中的范围：[p+1, r1]
    // 右子树在后序中的范围：[l2 + p - l1, r2 - 1]
    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;
}

调试建议： 在编写此类递归函数时，建议先在纸上画出小规模的例子（如只有 3 个节点），手动推导一次参数变化，确认区间计算公式无误后再上机验证。