Sum of Left Leaves

Posted on | Edited on | In | | Views:

Sum of Left Leaves

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

输入一棵二叉树, 返回所有左叶子的和.

Example:

   3
 /   \
9     20
     /   \
   15     7

其中, 左叶子为 9, 15, 所以返回 24

思路

遍历二叉树, 把左叶子存下来. 那么怎么定义左叶子呢? 一句话, 当root.left不为空且root.left.left和root.left.right为空的时候, root.left就是一个左叶子

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
def traversal(root):
    res = list()
    if not root:
        return res
    if root.left is not None and root.left.left is None and root.left.right is None:
        res.append(root.left.val)
    res += traversal(root.left)
    res += traversal(root.right)
    return res

def SumOfLeftLeaves(root):
    leaves = traversal(root)
    return sum(leaves)

复杂度

$O(n)$, $n$为二叉树节点个数.

EOF