本章节聚焦算法题实战，系统讲解算法模块。以题带点，通过代码实现帮助大家快速提升代码能力。
一、二叉树深度求解
题目背景
链接：二叉树深度
核心思路
计算二叉树高度其实是个经典的递归场景。直观理解，一棵树的高度等于左右子树高度的最大值再加一（根节点本身）。
这里有个关键点要注意：如果当前节点为空，返回 0 作为基准情况。在递归过程中，我们不需要构建复杂的树结构，直接利用数组存储的左右孩子索引即可遍历。这种基于数组的存储方式在处理完全二叉树或给定父子关系时非常高效。
代码实现
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int l[N], r[N]; // 分别存储左孩子和右孩子的索引
// 深度优先搜索计算高度
int dfs(int root) {
if (!root) return 0; // 空节点高度为 0
// 递归计算左右子树高度，取最大值并加 1
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; // 从根节点 1 开始计算
return 0;
}
二、求先序排列
题目背景
链接：求先序排列
核心思路
这道题考察的是根据中序和后序序列还原先序序列。处理这类问题的关键在于定位根节点。
在后序遍历中，最后一个元素一定是整棵树的根节点。找到这个根节点后，在中序遍历序列里就能把它切开，左边是左子树的中序，右边是右子树的中序。知道了左子树的长度，就能对应到后序序列中去划分左右子树的后序区间。
这个过程天然适合递归。每次递归确定当前区间的根节点，输出它，然后递归处理左右子树。注意边界条件的判断，当区间无效时直接返回。
代码实现
#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;
}
总结
这两道题的核心都在于递归思想的运用。前者通过递归求左右子树高度取最大值加一得出结果，后者利用中序与后序序列定位根节点，递归处理左右子树完成先序输出。算法学习没有捷径，每一道题的积累都是成长的阶梯。坚持刷题、沉淀思路，终会突破瓶颈。
