前言
二叉树是数据结构中的基础模型，理解其遍历与性质对算法进阶至关重要。本节通过两道经典题目，深入探讨递归在树形结构中的应用。
一、二叉树深度
1. 题目描述
给定一棵二叉树的节点编号及左右子节点关系，计算树的最大深度。参考洛谷 P4913。
2. 思路分析
二叉树的高度定义为从根节点到最远叶子节点的最长路径上的节点数。对于任意节点，其高度等于左右子树高度的最大值加一。若节点为空，高度为 0。这种天然的结构非常适合使用深度优先搜索（DFS）进行递归求解。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int l[N], r[N];
// 递归计算以 root 为根的子树高度
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];
cout << dfs(1) << endl;
return 0;
}
注意这里使用了数组模拟链表存储树结构，适合节点编号连续的场景。递归出口处理空节点返回 0，避免越界。
二、求先序排列
1. 题目描述
已知一棵二叉树的中序遍历和后序遍历序列，求其先序遍历序列。参考洛谷 P1030。
2. 思路分析
这是经典的'由遍历序列还原二叉树'问题。关键在于定位根节点：
