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

Steven included in Leetcode Golang

2021-08-29 264 words 2 minutes

/leetcode104_binarytree/golang_leetcode.png

Contents

104. Maximum Depth of Binary Tree

Level : Easy

原題連結 : Click

題目 :

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example :

Note

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 3

Example 2:

Input: root = [1,null,2] Output: 2

Example 3:

Input: root = [] Output: 0

Example 4:

Input: root = [0] Output: 1

解題思路 :

這題的解法也屬於可以用queue和bfs概念做出來的題目
一樣是把每一個level的node當作一round，將node丟進queue裡，直到queue沒有東西了，代表已經到底了

queue解法

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

Runtime: 4 ms, faster than 90.28% of Go online submissions for Maximum 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(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)
        
        for i := 0; i < length; i++ {
            
            node := queue[0]
            
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            
            queue = queue[1:]
        }
        
        depth++
    }
    
    return depth
    
}

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