# 404. Sum of Left Leaves 左叶子之和

@TOC

[LeetCode]

• Difficulty: Easy

## # 题目大意

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

## # 解题方法

### # 递归

Java解法是这样的。

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int sum=0;
public int sumOfLeftLeaves(TreeNode root) {
if(root==null){
return 0;
}
if(root.left!=null){
if(root.left.left==null && root.left.right==null){//根的左边节点是叶子
sum += root.left.val;//加上左叶子的值
}
sumOfLeftLeaves(root.left);//循环左叶子
}
if(root.right!=null){
sumOfLeftLeaves(root.right);//循环右叶子
}

return sum;
}
}
``````

AC：8 ms

``````public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null){
return 0;
}
int sum=0;
if(root.left!=null){
if(root.left.left==null && root.left.right==null){
sum += root.left.val;
}else{
sum += sumOfLeftLeaves(root.left);
}
}

sum += sumOfLeftLeaves(root.right);

return sum;
}
}
``````

AC:9 ms

Python解法是这样的。

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
self.sum = 0
self.inOrder(root)
return self.sum

def inOrder(self, root):
if not root: return
if root.left:
self.inOrder(root.left)
if not root.left.left and not root.left.right:
self.sum += root.left.val
if root.right:
self.inOrder(root.right)
``````

### # 迭代

Python解法如下：

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
stack = []
stack.append(root)
leftsum = 0
while stack:
node = stack.pop()
if not node: continue
if node.left:
if not node.left.left and not node.left.right:
leftsum += node.left.val
stack.append(node.left)
if node.right:
stack.append(node.right)
return leftsum
``````

## # 日期

2017 年 1 月 7 日 2018 年 11 月 14 日 —— 很严重的雾霾