首页天道酬勤二叉树的层次节点(二叉树层序遍历)

二叉树的层次节点(二叉树层序遍历)

admin 12-04 05:41 147次浏览

题目:很简单。

原标题[1]

今天继续更新剑指的优惠系列。像往常一样,每天下午6: 45准时更新微信官方账号的精选算法题。记得关注一下~另外,在微信官方账号回复报价,可以看到剑指优惠系列当前系列的所有文章。

00-1010输入二叉树的根节点,找到树的深度。从根节点到hxdxf依次经过的节点(包括根和hxdxf)构成了树的路径,最长的路径就是树的深度。

节点总数=1000

题目描述

题目样例

给定二叉树[3,9,20,null,null,15,7],

/\

920

/\

157

返回其最大深度3。

示例

如果限制只能递归或迭代,如何解决?00-1010

题目思考

解决方案

首先考虑递归方法,尝试DFS。我们可以构造递归方法3360来传入节点并返回当前节点的深度,这是左右子树的最大深度。1假设叶节点的深度为1,很明显根节点的深度是整棵树的最大深度,也就是节点为空时,此时深度为0.

方案 1

的时间复杂度O(N):需要遍历整棵树。空间复杂度o (h) 3360h表示树的高度,即递归栈消耗0.10-1010类解3360。

defmaxDepth(自我,根:重新编码)-int:

ifnotroot:

#递归退出,空节点情况

返回0

#当前节点深度是左右子树1的最大深度

return 1 max(self . MaxDepth(root . left),self.maxDepth(root.right))

#还可以进一步简化为只有一行代码。

#返回0 ifnotrootelse1 max (self。maxdepth (root.left),self。maxdepth(root . right))

思路

复杂度

如果要求迭代实现,那么方案一就不行。一般来说,BFS可以先审判。这个问题也不例外。显然,这里的深度指的是BFS层数,所以你可以使用剑指Offer 32-II。从上到下打印二叉树II-leetcode剑指offer系列得到层数,但不需要打印出每一层的节点。数数层数就行了。不清楚的同学可以先看看那个问题的思路~下面的代码详细讲解了必要的步骤,让大家了解

代码

O(N):的时间复杂度,需要遍历整棵树空间复杂度O(N):以及队列

方案 2

classSolution:的空间消耗。

defmaxDepth(自我,根:重新编码)-int:

ifnotroot:

返回0

q=[根]

res=0

while eq :

#当前层中的节点数

柯林=伦(q)

fornodeinq[:柯林]:

#仅追加非空节点。

ifnode.left:

q.append(节点. left)

ifnode.right:

q.append(节点. right)

#队列切片,开始处理下一层

q=q[卷发器:]

#完成当前层的遍历,深度1

res=1

returnres

思路

[1]

原始链接: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

什么是亦庄盘古机房?如何开发vue-dev-serverJava0基础_day11-抽象类与接口雷士灯具管理系统
web前端开发新技术(web前端新技术) 二叉树面试知识点(二叉树 面试题)
相关内容