当前位置: 首页 > 后端技术 > Python

力扣-0559.N叉树的最大深度【Python】

时间:2023-03-26 17:50:46 Python

题目LeetCode给定一棵n叉树,求它的最大深度。最大深度是从根节点到最远节点的最长路径上的节点数叶子节点。Nary-Tree输入序列化表示在它们的levelordertraversal中,每组children由null值分隔(见示例)。示例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约束条件:n叉树的深度小于等于1000,节点总数在[0,104]之间。给定一棵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,10^4]之间。思路DFSPython3代码"""#Node.class节点的定义:def__init__(self,val=None,children=None):self.val=valself.children=children"""classSolution:defmaxDepth(self,root:'Node')->int:#DFSifnotroot:return0depth=0forchildinroot.children:depth=max(self.maxDepth(child),depth)returndepth+1BFSPython3代码"""#Node.class节点的定义:def__init__(self,val=None,children=None):self.val=valself.children=children"""class解决方案:defmaxDepth(self,root:'Node')->int:#BFSimportcollections#特判,不写会报错ifnotroot:return0q=collections.deque()q.append(root)depth=0whileq:for_inrange(len(q)):node=q.popleft()forchildinnode.children:q.append(child)depth+=1返回深度GitHublinkPython