404.md

Question:

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

Analysis

关于二叉树，当然首选递归了。

如果是任意一个节点，它会存在以下几个情况：

1. 它是空的
2. 它是叶子节点
3. 它不是叶子节点

如果它不是叶子节点的话，又会分出三种情况，鉴于本题重点在于，求左叶子节点的和，因而，第三种情况可以不去区分了，因为我们只关心有没有左叶子节点的值可以加。

当然了，实在要区分的也是可以的，这就造就了解法二，这是一个看似直观，实际更加复杂了的解法。

推荐解法一。

Tips

Code

// 解法一

func isLeaf(n *TreeNode) bool { return n != nil && n.Left == nil && n.Right == nil }

func sumOfLeftLeaves(root *TreeNode) int { if root == nil { return 0 }

    if isLeaf(root.Left) {
            return root.Left.Val + sumOfLeftLeaves(root.Right)
    }

    return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)

}

// 解法二

func sumOfLeftLeavesCore(root *TreeNode, rootIsLeft bool) int { if root == nil { return 0 }

    if rootIsLeft {
            if root.Left == nil && root.Right == nil {
                    return root.Val
            }
            return sumOfLeftLeavesCore(root.Left, true) + sumOfLeftLeavesCore(root.Right, false)
    }

    return sumOfLeftLeavesCore(root.Left, true) + sumOfLeftLeavesCore(root.Right, false)

}

func sumOfLeftLeaves2(root *TreeNode) int { if root == nil { return 0 }

    return sumOfLeftLeavesCore(root, false)

}