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)

  1. 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:

img

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

  1. Use recursive processing

  2. Dive into root left and right respectively, and return when none is reached.

  3. If neither left or right is none, return the smaller of the returned totals.

  4. 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

I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried LeetCode every day 7. Reverse Integer (Python, Go)
I tried LeetCode every day 112. Path Sum (Python, Go)
I tried LeetCode every day 20. Valid Parentheses (Python, Go)
I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
I tried LeetCode every day 13. Roman to Integer (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 21. Merge Two Sorted Lists (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)
I tried LeetCode every day 121 Best Time to Buy and Sell Stock (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
I tried Grumpy (Go running Python).
Let Code Day7 starting from zero "104. Maximum Depth of Binary Tree"
[Python / DynamoDB / boto3] List of operations I tried
I tried hundreds of millions of SQLite with python
I tried running faiss with python, Go, Rust
Python practice 100 knocks I tried to visualize the decision tree of Chapter 5 using graphviz
I tried to summarize how to use matplotlib of python
[OpenCV / Python] I tried image analysis of cells with OpenCV
[Python] I tried to get Json of squid ring 2
I tried using Python (3) instead of a scientific calculator
I tried "morphology conversion" of images with Python + OpenCV
I tried to summarize the string operations of Python
I tried Python> autopep8
I tried Python> decorator
I tried to find the entropy of the image with python
I tried "gamma correction" of the image with Python + OpenCV
Let Code Day 44 "543. Diameter of Binary Tree" starting from zero
I tried the accuracy of three Stirling's approximations in python
I tried running Movidius NCS with python of Raspberry Pi3
Automatic scraping of reCAPTCHA site every day (1/7: python environment construction)
[Python] I tried to visualize the follow relationship of Twitter
[Python] I tried collecting data using the API of wikipedia
I tried to fight the Local Minimum of Goldstein-Price Function
I tried a stochastic simulation of a bingo game with Python
I tried to implement blackjack of card game in Python
I tried scraping with Python
I tried Python C extension
[Python] I tried using OpenPose
I tried gRPC with Python
I tried scraping with python
I tried scraping the ranking of Qiita Advent Calendar with Python
I tried to make a regular expression of "amount" using Python
I tried to make a regular expression of "time" using Python
I tried to create a list of prime numbers with python
I tried to make a regular expression of "date" using Python
I tried to fix "I tried stochastic simulation of bingo game with Python"
I tried to improve the efficiency of daily work with Python
I tried to automatically collect images of Kanna Hashimoto with Python! !!
I tried to make a mechanism of exclusive control with Go