[Golang][Leetcode][BinaryTree]刷題系列-104-Minimum Depth of Binary Tree

Steven included in Leetcode Golang

2021-08-29 276 words 2 minutes

/leetcode111_binarytree/golang_leetcode.png

Contents

111. Minimum Depth of Binary Tree

Level : Easy

原題連結 : Click

題目 :

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.

Example :

Note

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

解題思路 :

這題的解法可以參考 leetcode104題解，我使用同樣queue的解法，只是多做了一個判斷當有一個node沒有left children & right children時，直接回傳depth，因為那便是最小深度

queue解法

time complexity: O(n) , space complexity: O(n)

Runtime: 184 ms, faster than 98.29% of Go online submissions for Minimum Depth of Binary Tree.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    
    if root == nil {
        return 0
    }
    
    var queue []*TreeNode
    
    queue = append(queue,root)
    
    var depth int
    
    
    for len(queue) != 0 {
        
        length := len(queue)
        depth++

        for i := 0; i < length; i++ {
            
            check := 0
            
            node := queue[0]
            
            if node.Left != nil {
                queue = append(queue, node.Left)
                check++
            }
            
            if node.Right != nil {
                queue = append(queue, node.Right)
                check++
            }
            
            if check == 0 {
                return depth
            }
            
            queue = queue[1:]
        }
        
    }
    
    return depth
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!