二叉树深度求解与中后序转先序实战

二、求先序排列

题目背景

链接：求先序排列

核心思路

这道题考察的是根据中序和后序序列还原先序序列。处理这类问题的关键在于定位根节点。

在后序遍历中，最后一个元素一定是整棵树的根节点。找到这个根节点后，在中序遍历序列里就能把它切开，左边是左子树的中序，右边是右子树的中序。知道了左子树的长度，就能对应到后序序列中去划分左右子树的后序区间。

这个过程天然适合递归。每次递归确定当前区间的根节点，输出它，然后递归处理左右子树。注意边界条件的判断，当区间无效时直接返回。

代码实现

#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++;
    
    // 递归处理左子树
    // 左子树中序范围：[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;
}

总结

这两道题的核心都在于递归思想的运用。前者通过递归求左右子树高度取最大值加一得出结果，后者利用中序与后序序列定位根节点，递归处理左右子树完成先序输出。算法学习没有捷径，每一道题的积累都是成长的阶梯。坚持刷题、沉淀思路，终会突破瓶颈。