二叉树的层次节点(二叉树层序遍历)
题目:很简单。
原标题[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/