Leetcode/F家 -- 404. Sum of Left Leaves (BFS + DFS)

404. Sum of Left Leaves(BFS + DFS)
Easy
https://leetcode.com/problems/sum-of-left-leaves/

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

思路1： BFS, just make sure left node is leaf(cur.left & cur.right == null) when adding to the sum
Complexity: O(N)time

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){ return 0;}
        int sum = 0;
        LinkedList<TreeNode> qu = new LinkedList<TreeNode>();
        qu.add(root);
        while (!qu.isEmpty()){
            TreeNode cur = qu.remove();
            if(cur.left != null){
                qu.add(cur.left);
                if(cur.left.left == null && cur.left.right == null)//make sure leaf node
                    sum += cur.left.val;
            }
            if(cur.right != null){
                qu.add(cur.right);
            }
        }
        return sum;
    }
}

思路2： DFS, same as above need to check leaf property

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){ return 0;}
        int sum = 0;
        if(root.left!=null){
             if(root.left.left == null && root.left.right == null){ sum += root.left.val;}//make sure left child leaf
        }
        sum += sumOfLeftLeaves(root.left);
        sum += sumOfLeftLeaves(root.right);
        
        return sum;
    }
   
}