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

注意这里使用数组模拟树结构，l 和 r 分别存储左右孩子编号，避免了动态内存分配，效率较高。

二、求先序排列

题目描述

已知一棵二叉树的中序遍历和后序遍历序列，求其先序遍历结果。参考题目链接：洛谷 P1030 求先序排列

思路解析

这道题的关键在于利用后序遍历的'根在末尾'特性定位根节点，再结合中序遍历划分左右子树范围。

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

    // 计算左子树长度
    int leftLen = p - l1;

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

    // 递归处理右子树
    // 中序：[p+1, r1]
    // 后序：[l2+leftLen, r2-1]
    dfs(p + 1, r1, l2 + leftLen, r2 - 1);
}

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

实际编码时，区间计算容易出错，建议画图辅助确认下标变化。这段代码直接输出了先序序列，没有构建实际的树结构，空间复杂度更优。

总结

这两个问题都体现了递归在树形结构处理中的核心地位。第一个问题关注高度统计，第二个问题关注序列还原。在刷题过程中，多画图分析边界情况，能显著减少下标错误的发生。