## Monday, September 26, 2016

### LeetCode 404 - Sum of Left Leaves

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.```
X. DFS
https://discuss.leetcode.com/topic/60434/java-clean-no-helper-recursive/2
``````    public int sumOfLeftLeaves(TreeNode n) {
if(n==null ||(n.left==null && n.right ==null))return 0;
int l=0,r=0;
if(n.left!=null)l=(n.left.left==null && n.left.right==null)?n.left.val:sumOfLeftLeaves(n.left);
if(n.right!=null)r=sumOfLeftLeaves(n.right);
return l+r;
}``````
https://discuss.leetcode.com/topic/60403/java-iterative-and-recursive-solutions
``````public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int ans = 0;
if(root.left != null) {
if(root.left.left == null && root.left.right == null) ans += root.left.val;
else ans += sumOfLeftLeaves(root.left);
}
if(root.right != null) {
ans += sumOfLeftLeaves(root.right);
}

return ans;
}``````
X. DFS - V2
https://discuss.leetcode.com/topic/60364/easy-java-solution-with-comment
``````    public int sumOfLeftLeaves(TreeNode root) {
return helper(root, false);
}

private int helper(TreeNode root, boolean isLeft){
if(root == null) return 0;
/*This node is a leaf, if it's a left leaf, we return the value
if it's a right leaf we return 0 since right leaf doesn't count*/
if(root.left == null && root.right == null){
if(isLeft){
return root.val;
}
return 0;
}
return helper(root.left, true) + helper(root.right, false);
}  ``````
X. DFS Iterative Version
https://discuss.leetcode.com/topic/60403/java-iterative-and-recursive-solutions
Iterative method. Here for each node in the tree we check whether its left child is a leaf. If it is true, we add its value to answer, otherwise add left child to the stack to process it later. For right child we add it to stack only if it is not a leaf.
``````public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int ans = 0;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);

while(!stack.empty()) {
TreeNode node = stack.pop();
if(node.left != null) {
if (node.left.left == null && node.left.right == null)
ans += node.left.val;
else
stack.push(node.left);
}
if(node.right != null) {
if (node.right.left != null || node.right.right != null)
stack.push(node.right);
}
}
return ans;
}``````
https://discuss.leetcode.com/topic/60415/java-solution-with-stack
``````    public int sumOfLeftLeaves(TreeNode root) {
int res = 0;

Stack<TreeNode> stack = new Stack<>();
stack.push(root);

while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
if (node.left != null && node.left.left == null && node.left.right == null)
res += node.left.val;
stack.push(node.left);
stack.push(node.right);
}
}

return res;
}``````

X. BFS
https://discuss.leetcode.com/topic/60381/java-solution-using-bfs
``````    public int sumOfLeftLeaves(TreeNode root) {
if(root == null || root.left == null && root.right == null) return 0;

int res = 0;
queue.offer(root);

while(!queue.isEmpty()) {
TreeNode curr = queue.poll();

if(curr.left != null && curr.left.left == null && curr.left.right == null) res += curr.left.val;
if(curr.left != null) queue.offer(curr.left);
if(curr.right != null) queue.offer(curr.right);
}
return res;
}``````