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

How to analyze the minimum depth of python binary tree, I believe that many inexperienced people do not know what to do. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

Topic description

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]

three

/\

9 20

/\

15 7

Returns its minimum depth 2.

The idea of solving the problem

Tag: DFS

Termination conditions, return values, and recursive procedures:

If the root of the current node is empty, the height of the tree here is 0 and 0 is also the minimum.

When both the left and right subtrees of the current node root are empty, it means that the height of the tree here is 1 and 1 is also the minimum

If it is otherwise, it means that the current node has a value, and the minimum depth of its left and right subtrees needs to be calculated respectively. Returning the minimum depth + 1 means that there is 1 depth in the current node.

Time complexity: O (n), n is the number of nodes in the tree

Code

Java version

/ * *

* Definition for a binary tree node.

* public class TreeNode {

* int val

* TreeNode left

* TreeNode right

* TreeNode (int x) {val = x;}

*}

, /

Class Solution {

Public int minDepth (TreeNode root) {

If (root = = null) {

Return 0

}

If (root.left = = null & & root.right = = null) {

Return 1

}

Int ans = Integer.MAX_VALUE

If (root.left! = null) {

Ans = Math.min (minDepth (root.left), ans)

}

If (root.right! = null) {

Ans = Math.min (minDepth (root.right), ans)

}

Return ans + 1

}

}

JavaScript version

/ * *

* Definition for a binary tree node.

* function TreeNode (val) {

* this.val = val

* this.left = this.right = null

*}

, /

/ * *

* @ param {TreeNode} root

* @ return {number}

, /

Var minDepth = function (root) {

If (root = = null) {

Return 0

}

If (root.left = = null & & root.right = = null) {

Return 1

}

Let ans = Number.MAX_SAFE_INTEGER

If (root.left! = null) {

Ans = Math.min (minDepth (root.left), ans)

}

If (root.right! = null) {

Ans = Math.min (minDepth (root.right), ans)

}

Return ans + 1

}

Drawing and interpretation

After reading the above, do you know how to parse the minimum depth of the python binary tree? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

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.