leetcode404(左叶子之和)–Java语言实现

求：

计算给定二叉树的所有左叶子之和。

示例：

    3
   /
  9  20
    /  
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

题目链接： https://leetcode-cn.com/problems/sum-of-left-leaves/

解：

1、深度优先搜索（DFS）

递归实现深度优先搜索，使用一个标志位left标识当前节点是否是左孩子节点，如果发现某个节点是左孩子节点，且是叶子节点，则增加sum的值。最后返回sum。

时间复杂度：O(N)

空间复杂度：O(N)

private Integer sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
    Traverse(root,false);
    return sum;
}

private void Traverse(TreeNode root,Boolean left){
    if(root==null)  return;
    if(left && root.left==null && root.right==null) sum += root.val;
    Traverse(root.left,true);
    Traverse(root.right,false);
}