二叉树算法实战：计算深度与先序遍历还原

二、求先序排列

题目背景

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

思路解析

核心在于利用后序遍历的'尾元素是根节点'这一特性。

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];

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

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

总结

这两道题都体现了分治思想在树形结构中的应用。第一题关注高度统计，第二题关注序列重构。掌握递归参数的传递逻辑是解决此类问题的关键。实际编码时，建议先在纸上画出区间变化过程，确认边界条件无误后再编写代码。