牛客13279题BFS解法：5步掌握树的高度计算技巧 算法详解

一、题目解读

牛客13279题是经典的树结构基础题目，要求计算给定树的高度。题目输入为树的节点数和父子关系，输出树的最大深度。该题考察对树遍历算法的掌握程度，是面试和竞赛中的高频考点。

二、解题思路分析

采用广度优先搜索(BFS)算法，核心思想是按层遍历树节点：

1. 从根节点开始逐层向下搜索

2. 每完成一层遍历，高度计数器加1

3. 使用队列数据结构实现BFS

4. 时间复杂度O(n)，空间复杂度O(n)

三、解题步骤详解

1. 初始化队列并将根节点入队

2. 记录当前层的节点数量

3. 处理当前层所有节点，将其子节点入队

4. 完成一层处理后高度+1

5. 重复直到队列为空

四、完整代码实现（带注释）

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

int computeHeightBFS(const vector<vector<int>>& tree) {
    if (tree.empty()) return 0;  // 空树高度为0

    queue<int> q;
    q.push(0);  // 根节点入队
    int height = 0;

    while (!q.empty()) {
        int levelSize = q.size();  // 当前层节点数
        while (levelSize--) {      // 处理当前层所有节点
            int node = q.front();
            q.pop();
            for (int child : tree[node]) {
                q.push(child);  // 子节点入队
            }
        }
        height++;  // 完成一层遍历
    }
    return height;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;  // 节点数
    cin >> n;
    vector<vector<int>> tree(n);  // 树的邻接表表示

    // 构建树结构
    for (int i = 0; i < n - 1; ++i) {
        int parent, child;
        cin >> parent >> child;
        tree[parent].push_back(child);
    }

    cout << computeHeightBFS(tree) << endl;
    return 0;
}

五、总结

本文详细讲解了牛客13279题的BFS解法，通过队列实现树的层次遍历，代码简洁高效。该方法时间复杂度为线性，适合处理大规模树结构问题。