Shulou(Shulou.com)06/01 Report--

Today, I will talk to you about how to find the depth of the python binary tree, which may not be well understood by many people. In order to make you understand better, the editor has summarized the following contents for you. I hope you can get something from this article.

Topic description

Enter the root node of a binary tree to find the depth of the tree. The nodes (including root and leaf nodes) passing through in turn from the root node to the leaf node form a path of the tree, and the length of the longest path is the depth of the tree.

Total number of nodes int:

If not root:

# Recursive exit, the case of empty node

Return 0

# the current node depth is the maximum depth of the left and right subtrees + 1

Return 1 + max (self.maxDepth (root.left), self.maxDepth (root.right))

# can also be further simplified to require only one line of code..

# return 0 if not root else 1 + max (self.maxDepth (root.left), self.maxDepth (root.right))

If the idea of scheme 2 must be implemented in an iterative way, then scheme 1 is not good. Generally, iterations can try BFS first, and this problem is no exception through the analysis of the topic. Obviously, the depth here refers to the number of layers of BFS, so you can use the sword finger Offer 32-II. Printing binary tree II-leetcode from top to bottom refers to the offer series to get the number of layers, but you don't need to print out the nodes of each layer, you only need to count the number of layers. Students who are not clear can first take a look at the train of thought of that question. The following code explains the necessary steps in detail to facilitate understanding of complexity time complexity O (N): need to traverse the entire tree space complexity O (N): queue space consumption code class Solution:

Def maxDepth (self, root: TreeNode)-> int:

If not root:

Return 0

Q = [root]

Res = 0

While q:

# number of nodes in the current layer

Curlen = len (Q)

For node in q [: curlen]:

# append only non-empty child nodes

If node.left:

Q.append (node.left)

If node.right:

Q.append (node.right)

# queue slice, start processing the next layer

Q = Q [curlen:]

# traversal of the current layer is complete, depth + 1

Res + = 1

Return res

After reading the above, do you have any further understanding of how to find the depth of the python binary tree? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.