前言
二叉树是数据结构中的核心结构之一，掌握其遍历、属性计算及节点关系处理是算法进阶的关键。本节通过两道经典题目，分别探讨树的遍历重建以及深度、宽度与路径距离的计算方法。
一、美国血统（American Heritage）
题目背景
给定一棵二叉树的中序遍历和前序遍历序列，要求输出其后序遍历序列。这是典型的根据两种遍历序列还原树结构的问题。
解题思路
核心在于利用前序遍历确定根节点，再在中序遍历中找到该根节点的位置，从而划分左右子树范围。这是一个递归过程：
- 从前序序列中取出当前根节点。
- 在中序序列中定位该根节点，左侧为左子树，右侧为右子树。
- 递归处理左右子树，最后输出根节点（即后序遍历顺序）。
代码实现
#include <iostream>
#include <string>
using namespace std;
string a, b; // a 为中序，b 为前序
void dfs(int l1, int r1, int l2, int r2) {
// 递归窗口：l1,r1 是中序的左右边界，l2,r2 是前序的左右边界
if (l1 > r1) return;
// 寻找中序遍历中根节点的位置
int p = l1;
while (a[p] != b[l2]) p++;
// 递归处理左子树
// 左子树长度：p - l1
// 前序左子树起始位置：l2 + 1
dfs(l1, p - 1, l2 + 1, l2 + p - l1);
// 递归处理右子树
// 前序右子树起始位置：l2 + p - l1 + 1
dfs(p + 1, r1, l2 + p - l1 + 1, r2);
// 根节点（后序遍历：左 -> 右 -> 根）
cout << b[l2];
}
int main() {
cin >> a >> b;
(, a.() - , , b.() - );
;
}
