二叉树深度计算与先序序列还原算法实战

关键点在于区间的定位：

1. 根节点在后序序列的末尾。
2. 在中序序列中找到根节点下标 p。
3. 左子树长度即为 p - l1。
4. 根据长度偏移量更新递归时的区间边界。

代码实现

#include <iostream>
using namespace std;

string 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 - 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;
}

总结

这两道题虽然难度不同，但都深刻体现了递归的分治思想。二叉树深度侧重于高度聚合，而序列还原侧重于区间映射。在实际开发中，理解这些底层逻辑有助于优化树形数据的存储与查询效率。算法学习没有捷径，每一道题的积累都是成长的阶梯。