leetcode-404：左叶子之和

问题

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

示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

思路

首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历

其实题目说的也很清晰了，左和叶子我们都知道表示什么，那么左叶子也应该知道了，但为了大家不会疑惑，我还是来给出左叶子的明确定义：如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶子

这棵树的左叶子之和是0，因为这棵树根本没有左叶子！
那么，判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：

if (node.left != null && node.left.left == null && node.left.right == null) {
    //左叶子节点处理逻辑
}

解法一：递归

递归三部曲：

• 确定递归函数的参数和返回值
  • 判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int

• 确定终止条件

  if (root == NULL) return 0;
  

• 确定单层递归的逻辑

  • 当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和

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

解法二：广度优先搜索

class Solution{
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int sum = 0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null){
                if(node.left.left == null && node.left.right == null){
                    sum += node.left.val;
                }else{
                    queue.offer(node.left);
                }
            }
            if(node.right != null){
                if(node.right.left != null || node.right.right != null){
                    queue.offer(node.right);
                }
            }
        }
        return sum;
    }
}

时间复杂度：，其中 n 是树中的节点个数。
空间复杂度：。空间复杂度与广度优先搜索使用的队列需要的容量相关，为