Contents

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


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