二叉树算法实战：美国血统与公共祖先求解

二、二叉树基础问题

题目

链接： Luogu P3884

需要计算二叉树的深度、宽度以及两个节点的最近公共祖先距离。

算法思路

1. 深度：使用 DFS 递归计算每个节点的最大子树高度。
2. 宽度：使用 BFS 层序遍历，记录每一层的节点数最大值。
3. 距离/LCA：利用父指针数组向上回溯。对于两个节点 x 和 y，标记从 x 到根路径上的节点，然后从 y 向上找第一个被标记的节点即为最近公共祖先，结合路径长度可算出距离。

代码实现

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

const int N = 110;
vector<int> tree[N];
int fa[N];      // 父亲节点
int dest[N];    // 记录路径节点

// 计算深度
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.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++;
    }
    cout << 2 * dest[y] + len << endl;
    return 0;
}

这两道题涵盖了二叉树最核心的遍历与结构分析。理解递归的分治思想是解决此类问题的关键，而 BFS 与父指针的应用则展示了不同场景下的优化策略。多动手模拟数据流程，能更快掌握算法精髓。