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

思路解析

后序遍历的最后一个元素一定是整棵树的根节点。找到这个根节点在中序遍历中的位置，就可以将中序序列划分为左子树和右子树两部分。 有了左右子树的范围，就可以递归地确定左子树和右子树的先序序列。 关键点在于如何根据当前层级的根节点，准确计算出下一层递归时左右子树在两个序列中的起止下标。

代码实现

#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 len_left = p - l1;

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

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

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

实际编码时，下标计算容易出错，建议画图辅助确认区间边界。

总结

这两道题都体现了递归分治的思想。树形问题通常可以转化为'根节点 + 左子树 + 右子树'的模式。掌握递归的终止条件和状态转移（区间变化）是解决此类问题的关键。