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

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

2个月前 (07-15)

牛客13279题解:基于广度优先搜索(BFS)计算树高度的算法优化与代码实现 广搜 广度优先搜索 BFS算法 牛客题解 层序遍历 树结构 第1张

一、题目解读

牛客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;  
}

五、总结

BFS是求解树高度的经典方法,通过层序遍历避免递归开销,尤其适用于需要快速计算层级关系的场景。代码中通过队列管理节点遍历顺序,利用levelSize优化循环,确保每层节点完全处理后再递增高度。掌握该算法对树结构相关问题(如最短路径、层级统计等)具有重要价值。

原创内容 转载请注明出处

分享给朋友:

相关文章

牛客25665题详解:二叉树重建与三种遍历实现

牛客25665题详解:二叉树重建与三种遍历实现

一、题目解读牛客25665题要求根据给定的层序遍历和中序遍历序列重建二叉树,并输出:    1.所有叶子节点(从左到右)   &n...

洛谷P2346四子连珠游戏最短步数BFS解法详解

洛谷P2346四子连珠游戏最短步数BFS解法详解

一、题目解读洛谷P2346是一道经典的棋盘游戏问题,要求在一4x4黑白棋棋盘上,通过移动棋子使同色棋子形成四子一线(横、竖或对角线),计算达成目标所需的最少步数。题目考察BFS算法应用和状态空间搜索能...

牛客14496题解:括号最大深度问题(栈思想与代码优化)

牛客14496题解:括号最大深度问题(栈思想与代码优化)

一、题目解读牛客14496题要求计算给定括号字符串中的最大深度。例如,对于字符串 "(()())",最大深度为2。题目考察对括号嵌套结构的理解,以及如何通过编程找到最深嵌套层次。二...

牛客4577题解:滑动窗口解法

牛客4577题解:滑动窗口解法

一、题目解读牛客4577题要求处理多组测试数据,每组包含一个整数数组crimes和两个参数n(数组长度)、t(阈值)、c(窗口大小)。题目需要统计数组中所有长度恰好为c的子数组,其元素和不超过t的数量...

牛客13278题详解:句子单词反转(C++实现)

牛客13278题详解:句子单词反转(C++实现)

一、题目解读牛客13278题要求编写函数实现句子中单词顺序的反转,例如将"Hello World"转换为"World Hello"。需注意处理首尾空格、单词间空...

牛客REAL645题解:动态规划求解朋友聚会问题(三维DP+状态转移优化)

牛客REAL645题解:动态规划求解朋友聚会问题(三维DP+状态转移优化)

一、题目解读牛客REAL645题要求解决一个朋友聚会安排问题:用户需每天邀请不同朋友(A/B/C)聚会,总天数为n,求所有可能的安排方案数。题目核心在于组合数学与状态约束——每日选择不能与前一天重复,...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。