404. 左叶子之和

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

示例：

    3
   / \
  9  20
    /  \
   15   7

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

思路

二叉树问题基本上都可以递归解决。当前节点的所有左叶子之和等于左右子树的左叶子之和。

注意叶子节点不是孩子节点。

解法

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

    public int sumVal(TreeNode root, boolean leftFlag) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        if (leftFlag && root.left == null && root.right == null) {
            sum += root.val;
            return sum;
        }
        int leftSum = sumVal(root.left, true);
        int rightSum = sumVal(root.right, false);
        return leftSum + rightSum;
    }
}

优化

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
        //获取左叶子节点值
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { // 中
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
}