404. 左叶子之和

题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

解法一：DFS

错误代码 1

 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


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil || root.Left == nil && root.Right == nil {
        return 0
    }
    res, curDepth := 0, 0
    var dfs func(root *TreeNode, depth int)
    dfs = func(root *TreeNode, depth int) {
        if root != nil {
            depth++
            if root.Left == nil && root.Right == nil {
                if depth > curDepth {
                    res += root.Val
                    curDepth = depth
                }
                return
            }
            dfs(root.Left, depth)
            dfs(root.Right, depth)
        }
    }
    dfs(root, 0)
    return res
}

错误代码 2

 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


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil{
        return 0
    }
    res, curDepth := 0, 0
    var dfs func(root *TreeNode, depth int, isLeft bool)
    dfs = func(root *TreeNode, depth int, isLeft bool) {
        if root != nil {
            depth++
            if root.Left == nil && root.Right == nil {
                if depth > curDepth && isLeft {
                    res += root.Val
                    curDepth = depth
                }
                return
            }
            dfs(root.Left, depth, true)
            dfs(root.Right, depth, false)
        }
    }
    dfs(root, 0, false)
    return res
}

正确代码 1

 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


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    res := 0
    var dfs func(root *TreeNode, isLeft bool)
    dfs = func(root *TreeNode, isLeft bool) {
        if root != nil {
            if root.Left == nil && root.Right == nil {
                if isLeft {
                    res += root.Val
                }
                return
            }
            dfs(root.Left, true)
            dfs(root.Right, false)
        }
    }
    dfs(root, false)
    return res
}