Contents

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


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” 我們峰頂見!!!