Contents

[Golang][Leetcode][BinaryTree]刷題系列-404-Sum of Left Leaves


404. Sum of Left Leaves


Level : Easy

原題連結 : Click

題目 :

Given the root of a binary tree, return the sum of all left leaves.


Example :

Note

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 24 Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:

Input: root = [1] Output: 0


解題思路 :

  • 這題是用recursive的方式實現DFS的概念(大部分有關於leaves的題目都可以往DFS的方向去思考)
  • 題目需要把每一個left leaves加起來,判斷一個leave是否為left leaves就是他是否是上一個node的left children
  • 這裡提供兩個解法,兩個解法大同小異,一個是straight forward的去寫出邏輯判斷node.Left 跟 node.Left.Left 跟 node.Left.Right,另一個是在argument中加入一個boolean去判斷上一個該node是否是left children

Recursive解法-1

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

Runtime: 0 ms, faster than 100.00% of Go online submissions for Sum of Left Leaves.


 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func sumOfLeftLeaves(root *TreeNode) int {
    
    var sum int
    
    findLeftLeaves(root, &sum)
    
    return sum
    
}

func findLeftLeaves(node *TreeNode, sum *int) {
    
    if node.Left != nil && node.Left.Left == nil && node.Left.Right == nil {
        *sum += node.Left.Val
    }
    
    if node.Left != nil {
        findLeftLeaves(node.Left, sum)
    }
    
    if node.Right != nil {
        findLeftLeaves(node.Right, sum)
    }
}


Recursive解法-2

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

Runtime: 0 ms, faster than 100.00% of Go online submissions for Sum of Left Leaves.


 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {

    return getLeftLeavesSum(root, false)
}

func getLeftLeavesSum(node *TreeNode, isLeft bool) int {
    
    if node == nil {
        return 0
    }
    
    if node.Left == nil && node.Right == nil {
        if isLeft {
            return node.Val      
        }else {
            return 0
        }
    }
    
    leftSum := getLeftLeavesSum(node.Left, true)
    rightSum := getLeftLeavesSum(node.Right, false)
    
    return leftSum + rightSum
    
}


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