当前位置：首页 > 牛客 > 牛客13279题解：基于广度优先搜索（BFS）计算树高度的算法优化与代码实现

牛客13279题解：基于广度优先搜索（BFS）计算树高度的算法优化与代码实现

7小时前

一、题目解读

牛客13279题要求计算给定树的高度。树由n个节点组成，通过n-1条边连接，形成一棵有根树。题目核心在于高效求解树的高度，即从根节点到最深叶子节点的最长路径长度。需要理解树的结构特点，选择合适的算法策略。

二、解题思路

采用广度优先搜索（BFS）解题。BFS通过队列逐层遍历树节点，天然适合计算层级结构。从根节点开始，逐层扩展子节点，每遍历完一层高度递增，最终得到树的高度。该解法时间复杂度为O(n)，空间复杂度O(n)，适用于大规模数据。

三、解题步骤

1. 初始化队列，根节点入队。

2. 使用while循环，当队列非空时：

○ 记录当前层节点数量（levelSize）。

○ 循环levelSize次，弹出节点并遍历其子节点，子节点入队。

○ 每完成一层遍历，高度+1。

3. 返回最终高度。

四、代码与注释

#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++;  // 完成一层，高度+1  
    }  
    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;  
}