Sum of Left Leaves

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.leftroot.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