404 左叶子之和 简单
发布者:admin 发表于:417天前 阅读数:547 评论:0

404. 左叶子之和 简单

计算给定二叉树的所有左叶子之和。

示例:

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

代码参考:

package main

import "fmt"

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 9}
    root.Right = &TreeNode{Val: 20}
    root.Right.Left = &TreeNode{Val: 15}
    root.Right.Right = &TreeNode{Val: 7}

    //       3
    //   / \
    //  9  20
    //    /  \
    //   15   7
    fmt.Println(sumOfLeftLeaves(root)) // 24 // 9+15
}

// 左叶子则退出递归 ok
func sumOfLeftLeaves(root *TreeNode) int {
    var sum int
    traverse(root, &sum)
    return sum
}

func traverse(root *TreeNode, sum *int) {
    if root == nil {
        return
    }
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil { // 左叶子
        *sum += root.Left.Val // bingo
    }

    traverse(root.Left, sum)
    traverse(root.Right, sum)
}