当前位置:网站首页>[牛客网刷题 Day4] JZ55 二叉树的深度
[牛客网刷题 Day4] JZ55 二叉树的深度
2022-07-05 08:39:00 【strawberry47】
题目:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度,根节点的深度视为 1 。
思路:
第一次遇到树的题目,有一点点懵逼,不太懂他的构建过程
第一反应是用递归,因为结束的条件很容易想到嘛:左节点右节点都为空
but,我不知道应该怎么移动根节点耶。。。
答案:
看了答案,也用到了递归的思想:
有点懵。。递归好难啊o(╥﹏╥)o
class Solution:
def TreeDepth(self , pRoot: TreeNode) -> int:
# write code here
if not pRoot:
return 0
left = right =0
if pRoot.left:
left = self.TreeDepth(pRoot.left)
if pRoot.right:
right = self.TreeDepth(pRoot.right)
return max([left,right])+1
还可以用到队列的思想:
import queue
class Solution:
def maxDepth(self , root: TreeNode) -> int:
# 空节点没有深度
if not root:
return 0
# 队列维护层次后续节点
q= queue.Queue()
# 根入队
q.put(root)
# 记录深度
res = 0
# 层次遍历
while not q.empty():
# 记录当前层有多少节点
n = q.qsize()
# 遍历完这一层,再进入下一层
for i in range(n):
node = q.get()
# 添加下一层的左右节点
if node.left:
q.put(node.left)
if node.right:
q.put(node.right)
# 深度加1
res += 1
return res
队列的思路容易理解一些,就是将每一层都存进去,看看能存多少层,就加一
边栏推荐
- STM32 --- configuration of external interrupt
- 实例003:完全平方数 一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?
- EA introduction notes
- 实例010:给人看的时间
- Detailed summary of FIO test hard disk performance parameters and examples (with source code)
- 【日常訓練--騰訊精選50】557. 反轉字符串中的單詞 III
- Sword finger offer 09 Implementing queues with two stacks
- Yolov4 target detection backbone
- MATLAB小技巧(28)模糊綜合評價
- Guess riddles (6)
猜你喜欢
实例001:数字组合 有四个数字:1、2、3、4,能组成多少个互不相同且无重复数字的三位数?各是多少?
Arduino burning program and Arduino burning bootloader
猜谜语啦(4)
Typical low code apaas manufacturer cases
MySQL MHA high availability cluster
Guess riddles (10)
MATLAB skills (28) Fuzzy Comprehensive Evaluation
Digital analog 1: linear programming
Business modeling of software model | stakeholders
How apaas is applied in different organizational structures
随机推荐
Go dependency injection -- Google open source library wire
Low code platform | apaas platform construction analysis
猜谜语啦(10)
Some pitfalls of win10 network sharing
Search data in geo database
MySQL MHA high availability cluster
Bluebridge cup internet of things competition basic graphic tutorial - clock selection
Example 008: 99 multiplication table
L298N module use
Matlab tips (28) fuzzy comprehensive evaluation
轮子1:QCustomPlot初始化模板
696. Count binary substring
Shell script
Five design details of linear regulator
Wheel 1:qcustomplot initialization template
实例006:斐波那契数列
Example 002: the bonus paid by the "individual income tax calculation" enterprise is based on the profit commission. When the profit (I) is less than or equal to 100000 yuan, the bonus can be increase
Typescript hands-on tutorial, easy to understand
U8g2 drawing
Guess riddles (6)