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

二、二叉树问题

2.1 题目背景

针对给定的二叉树结构，需要求解三个指标：树的深度、树的宽度以及任意两节点间的距离（隐含最近公共祖先概念）。

2.2 解题思路

1. 深度（Depth）：使用深度优先搜索（DFS）。递归计算每个子树的最大深度，当前节点深度为子树最大深度加一。
2. 宽度（Width）：使用广度优先搜索（BFS）。按层遍历，记录每一层的节点数量，取最大值。
3. 距离与公共祖先：利用父亲指针数组 fa。从两个目标节点分别向上回溯到根节点，路径上的第一个交汇点即为最近公共祖先。距离等于两段路径长度之和减去两倍的重合部分。

注意：输入通常以父子关系对的形式给出，需先构建树结构并记录父节点信息，以便后续回溯。

2.3 参考实现

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

const int N = 110;
vector<int> tree[N]; // 邻接表存储树
int fa[N];           // 父节点数组
int dest[N];         // 记录 x 到 i 经历的节点个数

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

// 计算宽度：BFS
int bfs_width() {
    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_depth(1) << endl;
    // 输出宽度
    cout << bfs_width() << endl;

    // 计算两点距离
    int x, y;
    cin >> x >> y;
    
    // 标记 x 到根的路径
    while (x != 1) {
        dest[fa[x]] = dest[x] + 1;
        x = fa[x];
    }
    
    // 从 y 向上找，遇到已标记的点即为 LCA
    int len = 0;
    while (y != 1 && dest[y] == 0) {
        y = fa[y];
        len++;
    }
    
    // 总距离 = x 到 LCA + y 到 LCA
    cout << 2 * dest[y] + len << endl;
    
    return 0;
}

总结

这两道题涵盖了二叉树最基础也最重要的操作。第一题展示了如何利用遍历序列的数学性质进行递归构造，第二题则综合运用了 DFS、BFS 以及路径回溯技巧。在实际工程中，理解这些底层逻辑有助于优化树形数据的查询与处理性能。保持对基础算法的敏感度，是提升代码质量的关键。