Home Computer Science Java Algorithm

1254 · Sum of Left Leaves - LintCode

# Description

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

Example

Example 1

Input：
{3,9,20,#,#,15,7}
Output：24

Explanation：There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
    3
   / \
  9  20
    /  \
   15   7

Example 2:

Input:
{1,#,2,#,3}
Output:
0

Explanatinon:
1
  \
    2
      \
       3

# Solution

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: t
     * @return: the sum of all left leaves
     */
    public int sumOfLeftLeaves(TreeNode root) {
      if (root == null) return 0;
      int sum = 0;
      if (root.left != null){
      
          TreeNode left = root.left;
          // 如果左儿子为叶子节点
          if (left.left == null && left.right == null){
              sum += left.val;
          } else { // 否则继续递归遍历左子树
              sum += sumOfLeftLeaves(left);
          }
      } 
      // 递归遍历右子树
      if (root.right != null){
          TreeNode right = root.right;
          sum += sumOfLeftLeaves(right);
      }
      return sum;
    }
}