leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.
Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain. (Python is weak but experienced)
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
(Japanese translation)
Given a binary tree, find its minimum depth.
Minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
** Note: ** Leaf is a childless node
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Use recursive processing
Dive into root left and right respectively, and return when none is reached.
If neither left or right is none, return the smaller of the returned totals.
Finally, the minimum depth is used as the return value.
Answer code
class Solution:
def minDepth(self, root):
if root == None:
return 0
if root.left==None or root.right==None:
return self.minDepth(root.left)+self.minDepth(root.right)+1
return min(self.minDepth(root.right),self.minDepth(root.left))+1
--I'll write it in Go too!
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil {
return minDepth(root.Right) + 1
}
if root.Right == nil {
return minDepth(root.Left) + 1
}
return min(minDepth(root.Right), minDepth(root.Left)) + 1
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
Recommended Posts