[Golang][Leetcode][BinaryTree]刷題系列-513-Find Bottom Left Tree Value

Steven included in Leetcode Golang

2021-09-02 239 words 2 minutes

/leetcode513_binarytree/golang_leetcode.png

Contents

513. Find Bottom Left Tree Value

Level : Medium

原題連結 : Click

題目 :

Given the root of a binary tree, return the leftmost value in the last row of the tree.

Example :

Note

Example 1:

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

Example 2:

Input: root = [1,2,3,4,null,5,6,null,null,7] Output: 7

解題思路 :

這題需要你找到最後一排leave中最左邊的那個node的value
首先既然要找leave就必須使用dfs去把每一個leave visit一遍，並同時記錄該leave的level當遇到比當前紀錄的leave有更大的level時，替換掉他
這時候有些朋友可能會問那怎麼知道他是不是最左邊呢，這時候就可以用兩個小地方去控管
1. 這題的寫法需要將visit left node的recursive code寫在visit right node的前面，這樣就能確保他是從左邊開始visit到右邊
2. 因為是從左邊visit到右邊，所以我們需要當 maxLevel < curLevel 而不是 maxLevel <= curLevel時做替換，因為先visit的node必定比後進來的node還要左邊

Recursive解法

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

Runtime: 4 ms, faster than 96.55% of Go online submissions for Find Bottom Left Tree Value.

 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    
    res, maxLevel, curLevel := root.Val, -1, 0
    
    findBottomLeftLeave(root, &maxLevel, curLevel, &res)
    
    return res
}

func findBottomLeftLeave(node *TreeNode, maxLevel *int, curLevel int , res *int) {
    
    if node.Left == nil && node.Right == nil {
        if *maxLevel < curLevel {
            *maxLevel = curLevel
            *res = node.Val
        }
    }
    
    if node.Left != nil {
        findBottomLeftLeave(node.Left, maxLevel, curLevel+1, res)
    }
    
    if node.Right != nil {
        findBottomLeftLeave(node.Right, maxLevel, curLevel+1, res)
    }
}

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