左叶子之和（404）

题目： 计算给定二叉树的所有左叶子之和

示例：

思路分析–递归：
1.遍历二叉树，每次对根结点进行判断其是否有左叶子结点即可。
2.遍历方法可以采用前序 / 中序 /后序 /层次遍历。
3.算法步骤的关键点在于如何判断一个结点是否为左叶子结点，在确定该结点既无左子结点，亦无右子结点时，可以确定该结点为叶子结点，但无法确定该结点是否为左叶子结点，此时就要通过该结点的父结点进行确定性判断，该父结点不为空，且父结点的左孩子（即上文提到的该结点）不为空，且左孩子的左孩子与右孩子皆为空，故该结点为左叶子结点。

Code–递归

class Solution {
	int sum = 0; 
	public int sumOfLeftLeaves(TreeNode root) {
		if (root == null) { //递归出口
			return 0;
		}
		//判断是否为左叶子结点
		if (root.left != null && root.left.left == null && root.left.right == null){
			sum += root.left.val;
		}
		sumOfLeftLeaves(root.left);
		sumOfLeftLeaves(root,right);
		return sum;
	}
}

算法分析
1.时间复杂度O（N）：因为要遍历二叉树各个节点且只遍历一次。
2.空间复杂度O（N）：最坏的情况下，二叉树结构退化为链表结构，递归算法需要O（N）的栈辅助空间。

本题涉及知识点：java中的引用传递和值传递