当前位置:网站首页>[Niuke brush questions day4] jz55 depth of binary tree
[Niuke brush questions day4] jz55 depth of binary tree
2022-07-05 08:43:00 【strawberry47】
subject :
Enter a binary tree , Find the depth of the tree . The nodes that pass from the root node to the leaf node ( Containing root 、 leaf ) A path to a tree , The length of the longest path is the depth of the tree , The depth of the root node is treated as 1 .
Ideas :
First encounter the problem of trees , A little confused , I don't understand his construction process
The first reaction is to use recursion , Because the end condition is easy to think of : Both left and right nodes are empty
but, I don't know how to move the root node ...
answer :
Looking at the answer , The idea of recursion is also used :
mentally .. Recursion is so hard 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
You can also use the idea of queues :
import queue
class Solution:
def maxDepth(self , root: TreeNode) -> int:
# Empty nodes have no depth
if not root:
return 0
# Subsequent nodes of the queue maintenance hierarchy
q= queue.Queue()
# Root in the team
q.put(root)
# Record the depth
res = 0
# Level traversal
while not q.empty():
# Record how many nodes there are in the current layer
n = q.qsize()
# Traverse this layer , Go on to the next floor
for i in range(n):
node = q.get()
# Add the left and right nodes of the next layer
if node.left:
q.put(node.left)
if node.right:
q.put(node.right)
# Depth plus 1
res += 1
return res
The idea of queue is easier to understand , Is to save every layer , See how many layers you can save , Plus one
边栏推荐
- Chapter 18 using work queue manager (1)
- Redis实现高性能的全文搜索引擎---RediSearch
- 多元线性回归(梯度下降法)
- Is the security account given by Yixue school safe? Where can I open an account
- Halcon Chinese character recognition
- 第十八章 使用工作队列管理器(一)
- EA introduction notes
- 猜谜语啦(3)
- Example 001: the number combination has four numbers: 1, 2, 3, 4. How many three digits can be formed that are different from each other and have no duplicate numbers? How many are each?
- 猜谜语啦(10)
猜你喜欢
猜谜语啦(2)
Mathematical modeling: factor analysis
Shift operation of complement
Guess riddles (5)
Halcon affine transformations to regions
Sword finger offer 05 Replace spaces
Example 007: copy data from one list to another list.
Arduino burning program and Arduino burning bootloader
Guess riddles (7)
Sword finger offer 09 Implementing queues with two stacks
随机推荐
Run菜单解析
EA introduction notes
整形的分类:short in long longlong
【日常训练】1200. 最小绝对差
Example 003: a complete square is an integer. It is a complete square after adding 100, and it is a complete square after adding 168. What is the number?
[noi simulation] juice tree (tree DP)
Bluebridge cup internet of things competition basic graphic tutorial - clock selection
Guess riddles (4)
多元线性回归(梯度下降法)
Lori remote control LEGO motor
Some pitfalls of win10 network sharing
Daily question - input a date and output the day of the year
Affected tree (tree DP)
Business modeling | process of software model
Search data in geo database
每日一题——替换空格
Old Wang's esp8266 and old Wu's ws2818 light strip
[three tier architecture and JDBC summary]
UE pixel stream, come to a "diet pill"!
资源变现小程序添加折扣充值和折扣影票插件