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

In this issue, the editor will bring you about what is the minimum depth of the python binary tree. The article is rich in content and analyzes and describes it from a professional point of view. I hope you can get something after reading this article.

Find the minimum depth of binary tree

Given a binary tree, find out its minimum depth.

The minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node.

Note: a leaf node is a node that does not have child nodes.

Example:

Given binary tree [3pc9pr 20pr nullpr nullpr 15pc7]

Returns its minimum depth 2.

Complete the following code:

# Definition for a binary tree node.

# class TreeNode (object):

# def _ _ init__ (self, x):

# self.val = x

# self.left = None

# self.right = None

Class Solution (object):

Def minDepth (self, root):

"

: type root: TreeNode

: rtype: int

"

2 Analysis

At the beginning of the analysis process, let's look at a wrong solution and explain why it is wrong:

Class Solution (object):

Def minDepth (self, root):

"

: type root: TreeNode

: rtype: int

"

If not root:

Return 0

If not root.left and not root.right:

Return 1

Return 1 + min (self.minDepth (root.left), self.minDepth (root.right))

Consider the following binary tree:

Using the above code to return the minimum depth is 1, but in fact the minimum depth is 2, because the minimum depth is defined as the number of nodes on the shortest path from the root node to the nearest leaf node.

Why is there a problem with the above solution?

The reason is that there is a problem in the selection of recursive bases, and only the following two situations are considered:

A binary tree is a None binary tree with only one node

The recursive basis does not take into account the following two situations, which leads to an error:

three

In order to solve the problem correctly, the two kinds of recursive bases omitted above need to be taken into account:

# the following two cases of recursive bases must be taken into account:

If not root.left:

Return 1 + self.minDepth (root.right)

If not root.right:

Return 1 + self.minDepth (root.left)

The correct complete code is as follows:

Class Solution (object):

Def minDepth (self, root):

If not root:

Return 0

If not root.left and not root.right:

Return 1

# the following two cases of recursive bases must be taken into account:

If not root.left:

Return 1 + self.minDepth (root.right)

If not root.right:

Return 1 + self.minDepth (root.left)

Return 1 + min (self.minDepth (root.left), self.minDepth (root.right))

This is the minimum depth of the python binary tree shared by the editor. If you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

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.