二叉树深度计算与先序序列重构算法解析

前言

本文聚焦于二叉树的两个经典操作：计算树的最大深度，以及根据中序和后序遍历序列还原先序遍历。这两个问题都深刻体现了递归思想在树形结构处理中的核心作用。

二叉树深度

题目描述

给定一棵二叉树，求其最大深度（高度）。

核心思路

二叉树的高度定义为根节点到最远叶子节点的最长路径上的节点数。递归公式非常直观：

Height(root) = 1 + max(Height(left), Height(right))

若节点为空，高度为 0。通过 DFS 遍历整棵树即可得出结果。

代码实现

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

const int N = 1e6 + 10;
int l[N], r[N]; // 存储左右子节点索引

// 递归计算深度
int dfs(int root) {
    if (!root) return 0;
    return max(dfs(l[root]), dfs(r[root])) + 1;
}

int main() {
    int n;
    cin >> n;
    // 输入每个节点的左右子节点
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }
    // 从根节点 1 开始计算
    cout << dfs(1) << endl;
    return 0;
}

求先序排列

题目描述

已知一棵二叉树的中序遍历序列和后序遍历序列，求其先序遍历序列。

核心思路

后序遍历的最后一个元素一定是当前子树的根节点。找到该根节点在中序遍历中的位置，即可将中序序列划分为左子树和右子树部分。

1. 确定根节点（后序序列末尾）。
2. 在中序序列中找到根节点位置 p。
3. 递归处理左子树（中序 [l1, p-1]，后序对应区间）。
4. 递归处理右子树（中序 [p+1, r1]，后序对应区间）。
5. 输出顺序为：根 -> 左 -> 右。

代码实现

#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]，后序长度相同
    dfs(l1, p - 1, l2, l2 + p - l1 - 1);
    // 右子树：中序 [p+1, r1]，后序剩余部分
    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;
}

总结

这两道题是树形结构递归应用的典型代表。第一题考察对树高定义的理解，第二题考察序列特征与递归划分的结合。掌握这类问题的关键在于找准递归的终止条件和状态转移方程。在实际刷题中，建议多画图辅助理解区间变化，避免边界错误。