【Leetcode】404. Sum of Left Leaves

方法一：

思路：

大体上分为判断有没有左节点和有没有右节点。

(1)如果有左节点，看左节点有没有子节点，没有（即左叶子节点）则直接用起值去加，有则继续对左节点递归。

(2)如果有右节点，且右节点有子节点，则对右节点递归，否则不管是没有右节点还是右节点没有子节点（即右叶子节点）都直接看做加0。

需要注意的是：

(1)如果节点本身为0。

(2)如果根节点没有子节点，也要返回0，因为题目要求左叶子节点，根节点不算。

(5)在判断所有节点的子节点或者值之前，要对该节点本身是否为null做出判断。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public int sumOfLeftLeaves(TreeNode root) {        if (root == null)            return 0;        if (root.left == null && root.right == null)             return 0;        return ((root.left != null && root.left.left == null && root.left.right == null) ? root.left.val : sumOfLeftLeaves(root.left)) + ((root.right != null && (root.right.left != null || root.right.right != null)) ? sumOfLeftLeaves(root.right) : 0);    }}
Runtime：9ms
方法二：
思路：
/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    PRivate int sum = 0;    public int sumOfLeftLeaves(TreeNode root) {        dfs(root, false);        return sum;    }    void dfs(TreeNode root, boolean left) {        if (root == null)             return;        if (root.left == null && root.right == null)            sum = left ? sum + root.val : sum;        dfs(root.left, true);        dfs(root.right, false);    }}
Runtime：8ms