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

二、求先序排列

1. 题目描述

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

2. 算法原理

这是经典的「由后序和中序还原二叉树」问题。关键点在于确定根节点的位置：

1. 定位根节点：后序遍历的最后一个元素一定是当前子树的根节点。
2. 划分区间：在中序遍历中找到该根节点，其左侧为左子树的中序序列，右侧为右子树的中序序列。
3. 递归处理：根据中序序列的长度，在后序序列中对应切分出左、右子树的后序序列，递归构建。

注意边界条件：当区间无效（左 > 右）时直接返回。

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

    // 递归处理左子树
    // 左子树长度：p - l1
    // 后序左子树范围：[l2, l2 + (p - l1) - 1]
    dfs(l1, p - 1, l2, l2 + p - l1 - 1);

    // 递归处理右子树
    // 后序右子树范围：[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;
}

总结

这两道题的核心都在于递归思想的运用。第一题考察树的基本性质，第二题则涉及序列映射与区间划分。在实际刷题中，建议多画图辅助理解区间变化，避免下标越界。