二叉树算法实战：美国血统重建与深度宽度计算

前言

本章节聚焦算法题实战，通过两道经典题目系统讲解数据结构与算法核心模块。以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。

一、美国血统 American Heritage

1.1 题目

链接：美国血统 American Heritage

1.2 算法原理

这道题本质上是根据先序和中序遍历序列重建二叉树。解法同《求先序序列》，关键在于手动模拟一下过程，找出「相同子问题」，利用「递归」求解。

具体步骤如下：

1. 处理左右子树：确定当前根节点后，在中序序列中划分左右子树的范围。
2. 找根节点：在先序序列的第一个元素即为当前子树的根。
3. 划分左右子树：根据根节点在中序中的位置，递归处理左半部分和右半部分。

1.3 代码

#include <iostream>
using namespace std;

string a, b;

void dfs(int l1, int r1, int l2, int r2) {
    // 递归窗口
    if (l1 > r1) return;
    
    // 寻找中序遍历中根节点的位置
    int p = l1;
    while (a[p] != b[l2]) p++;
    
    // 递归处理左右子树
    dfs(l1, p - 1, l2 + 1, l2 + p - l1); // 左子树
    dfs(p + 1, r1, l2 + p - l1 + 1, r2); // 右子树
    
    // 根节点
    cout << b[l2];
}

int main() {
    cin >> a >> b;
    dfs(0, a.size() - 1, 0, b.size() - 1);
    return 0;
}

二、二叉树问题

2.1 题目

链接：二叉树问题

2.2 算法原理

这道题需要计算三个指标：深度、宽度和最近公共祖先（LCA）。

• 深度：使用递归 DFS 即可，取所有子树深度的最大值加一。
• 宽度：使用 BFS 宽搜，记录每一层的节点数，取最大值。
• 最近公共祖先：两点之间的距离可以通过向上不断找父亲结点来计算。第一个重叠的位置，就是两者的最近公共祖先。可以一边寻找，一边计算结果。

2.3 代码

// 二叉树问题
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 110;
vector<int> tree[N];
int fa[N];      // f[i]: i 的父亲节点
int dest[N];    // dest[i]: x 到 i 经历的节点个数

// 深度
int dfs(int u) {
    int ret = 0;
    for (auto v : tree[u]) ret = max(ret, dfs(v));
    return ret + 1;
}

// 宽度
int bfs() {
    queue<int> q;
    q.push(1);
    int ret = 0;
    while (q.size()) {
        int sz = q.size();
        ret = max(ret, sz);
        while (sz--) {
            auto x = q.front();
            q.pop();
            for (auto v : tree[x]) q.push(v);
        }
    }
    return ret;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        fa[v] = u;
    }

    // 深度
    cout << dfs(1) << endl;
    // 宽度
    cout << bfs() << endl;
    
    // 距离
    int x, y;
    cin >> x >> y;
    while (x != 1) {
        dest[fa[x]] = dest[x] + 1;
        x = fa[x];
    }
    int len = 0;
    while (y != 1 && dest[y] == 0) {
        y = fa[y];
        len++;
    }
    cout << 2 * dest[y] + len << endl;
    return 0;
}

总结

本章通过两道经典二叉树算法题，巩固了递归、深搜、宽搜等核心思想。从美国血统的遍历重建，到二叉树深度、宽度与公共祖先求解，每道题都在训练分治思维与代码实现能力。算法之路无捷径，坚持刷题、理清思路、动手实现，能力便会稳步提升。