二叉树深度计算与先序序列重构算法实战

注意：在递归划分时，需准确计算左右子树在后序序列中的对应区间边界，避免越界或逻辑错误。

代码实现

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

string in_order, post_order;

// l1, r1: 中序序列区间
// l2, r2: 后序序列区间
void dfs(int l1, int r1, int l2, int r2) {
    if (l1 > r1) return; // 区间无效直接返回

    // 后序序列的最后一个字符是根节点
    cout << post_order[r2];

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

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

    // 递归处理右子树
    // 右子树起始在后序中的位置：l2 + (p - l1)
    dfs(p + 1, r1, l2 + p - l1, r2 - 1);
}

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

总结

这两个问题都体现了递归思想在树形结构中的核心作用。前者通过自底向上聚合高度信息，后者通过根节点定位分割序列。在实际刷题中，建议多画图辅助理解区间变化，确保递归终止条件和参数传递无误。