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

二、二叉树问题

1. 题目描述

链接： 洛谷 P3884

给定一棵有根树，需要计算树的深度、宽度以及任意两点之间的距离（最近公共祖先相关）。

2. 算法原理

• 深度： 采用深度优先搜索（DFS），递归计算每个节点的最大子树高度。
• 宽度： 采用广度优先搜索（BFS），统计每一层的节点数，取最大值。
• 距离/最近公共祖先： 利用父亲数组向上回溯。两个点向上找到的第一个重叠位置即为最近公共祖先。可以通过标记路径或计算距离来优化查找过程。

3. 代码实现

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

const int N = 110;
vector<int> tree[N];
int fa[N];      // fa[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); // 假设根节点为 1
    int ret = 0;
    while (!q.empty()) {
        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;

    // 标记 x 到根的路径
    while (x != 1) {
        dest[fa[x]] = dest[x] + 1;
        x = fa[x];
    }

    // 从 y 向上找，直到遇到已标记的点
    int len = 0;
    while (y != 1 && dest[y] == 0) {
        y = fa[y];
        len++;
    }

    // 总距离 = 2 * 公共祖先深度 + y 到公共祖先的距离
    cout << 2 * dest[y] + len << endl;

    return 0;
}

总结

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