I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
What is Leetcode
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)
26th question (problem 111)
- Minimum Depth of Binary Tree
the issue's details
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
Way of thinking
-
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