首页 > 其他分享 >559. N 叉树的最大深度(bfs)

559. N 叉树的最大深度(bfs)

时间:2022-11-22 22:13:42浏览次数:50  
标签:Node 559 val int bfs 深度 null root children

给定一个 N 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)。

 

示例 1:

输入:root = [1,null,3,2,4,null,5,6]
输出:3

示例 2:

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:5

 

提示:

  • 树的深度不会超过 1000 。
  • 树的节点数目位于 [0, 104] 之间。

 

BFS经典模板。多了个dep记录层数。

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int ans=0;
    
    int maxDepth(Node* root) {
        queue<Node*> q;
        if(root==NULL) return 0;
        q.push(root);
        int dep=0;
        while(!q.empty())
        {
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                if(i==0) dep++;
                Node* front=q.front();
                q.pop();
            
                auto temp=front->children;
                for(int j=0;j<temp.size();j++)
                {
                    
                    q.push(temp[j]);
                }

            }
         
        }   
        ans=dep; 
        return ans;
    }
};

 

标签:Node,559,val,int,bfs,深度,null,root,children
From: https://www.cnblogs.com/zzzlight/p/16916662.html

相关文章

  • 深度解析KubeEdge EdgeMesh 高可用架构
    摘要:通过高可用特性应用场景、高可用特性使用手册、课题总结、未来展望等四个部分的内容来向大家介绍新版本EdgeMesh的高可用架构。本文分享自华为云社区《KubeEdgeEdgeM......
  • BFS和DFS
    BFS和DFS的对比​​BFS​​——queue实现——层序遍历空间是指数级别的大!!!不会有爆栈的风险找最短路径defBFS(graph,s):queue=[]queue.append(s)visited=......
  • 搜索与图论篇——DFS和BFS
    搜索与图论篇——DFS和BFS本次我们介绍搜索与图论篇中DFS和BFS,我们会从下面几个角度来介绍:DFS和BFS简介DFS数字排序DFS皇后排序DFS树的重心BFS走迷宫BFS八数码BFS......
  • 深度优先生成树和广度优先生成树的详解版
    其实在对无向图进行遍历的时候,遍历过程中所经历过的图中的顶点和边的组合,就是图的生成树或者生成森林。图1无向图 例如,图1中的无向图是由V1~V7的顶点和编号分......
  • 深度学习之tensorflow2实战:多输出模型
    欢迎来到CNN实战,尽管我们刚刚开始,但还是要往前看!让我们开始吧! 数据集链接:https://pan.baidu.com/s/1zztS32iuNynepLq7jiF6RA提取码:ilxh,请下载好数据,在开始 导入......
  • 深度学习算法基础
    1,基本概念1.1,余弦相似度1.2,欧式距离1.3,余弦相似度和欧氏距离的区别2,容量、欠拟合和过拟合3,正则化方法4,超参数和验证集5,估计、偏差和方差6,随机梯度下降算法......
  • 深度学习框架新手快速上手指南
    新手入门深度学习框架怎么办?快速、可拓展、易于使用且支持自动求导的深度学习框架-MegEngine配备了新手入门文档,助力初学者快速上手框架。文档借助了一系列的代码实战,有利......
  • 深度学习基础课程: 深度神经网络
    正文介绍在这节课中,我们将看到我们如何构建能够学习复杂关系的神经网络——深层神经网络以其著名。这里的关键思想是模块化,从简单的功能单元构建一个复杂的网络。我们已......
  • 必须经过关键点或达成某些状态的单源最短路-01bfs
    https://ac.nowcoder.com/acm/contest/45670/D题目描述:小竹成功从家里逃了出来,他决定去小胖家避一避。但是小胖要求小竹带一个刺激度大于xx的游戏才能去他家。为了防......
  • 论文阅读_基于深度学习的异常检测综述
    英文题目:DeepLearningforAnomalyDetection:AReview中文题目:基于深度学习的异常检测综述论文地址:https://arxiv.org/pdf/2007.02500.pdf领域:异常检测,深度学习发表......