package com.freetymekiyan.algorithms.level.easy;

import com.freetymekiyan.algorithms.utils.Utils.TreeNode;

/**
 * Find the sum of all left leaves in a given binary tree.
 * <p>
 * Example:
 * <p>
 * |    3
 * |   / \
 * |  9  20
 * |    /  \
 * |   15   7
 * <p>
 * There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
 * Company Tags: Facebook
 * Tags: Tree
 */
public class SumOfLeftLeaves {

    /**
     * DFS. Recursive.
     * Just change the visit of DFS.
     * Recurrence relation:
     * Current left leaf's value + sum of left subtree's leaves + sum to right subtree's leaves.
     * When visit, if current node's left child is not null, and it is a leaf.
     * Add its value to result.
     * Then call sum recursively on right subtree.
     * Base case:
     * If root is null, return 0.
     */
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { // root.left is a leave.
            sum += root.left.val; // Add directly to result.
        } else { // root.left is a subtree, recurse.
            sum += sumOfLeftLeaves(root.left);
        }
        sum += sumOfLeftLeaves(root.right);
        return sum;
    }

    /**
     * DFS. Recursive.
     * Pass another boolean to indication whether the call is from left.
     */
    public int sumOfLeftLeavesB(TreeNode root) {
        return dfs(root, false);
    }

    /**
     * DFS.
     * Two base cases:
     * 1) root is null, return 0.
     * 2) root not null, root is leaf. If from left, return value. Otherwise return 0.
     * The result is the left leaves sum of left subtree and right subtree.
     */
    private int dfs(TreeNode root, boolean isLeft) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return isLeft ? root.val : 0;
        }
        return dfs(root.left, true) + dfs(root.right, false);
    }

}

@@ -102,19 +102,131 @@
 eNode;%0A%0A
-/**
+import java.util.ArrayDeque;%0Aimport java.util.Queue;%0Aimport java.util.Stack;%0A%0A/**%0A * 404. Sum of Left Leaves%0A * %3Cp%3E
 %0A * Find
@@ -494,19 +494,29 @@
 book%0A * 
-Tag
+Related Topic
 s: Tree%0A
@@ -586,45 +586,8 @@
 ve.%0A
-     * Just change the visit of DFS.%0A
     
@@ -1165,18 +1165,17 @@
 is a lea
-ve
+f
 .%0A      
@@ -1552,17 +1552,17 @@
 ftLeaves
-B
+2
 (TreeNod
@@ -1642,21 +1642,17 @@
   * 
-Two b
+B
 ase case
 s:%0A 
@@ -1647,17 +1647,16 @@
 ase case
-s
 :%0A     *
@@ -1697,39 +1697,43 @@
  2) 
-root not null, root
+If current node
  is 
+a 
 leaf
-. If
+, and it's
  fro
@@ -1751,34 +1751,19 @@
 urn 
+it's 
 value.
- Otherwise return 0.
 %0A   
@@ -1784,16 +1784,23 @@
  is the 
+sum of 
 left lea
@@ -2139,10 +2139,1493 @@
 %0A    %7D%0A%0A
+    /**%0A     * Pre-order traversal with a stack.%0A     * For each node, check if it has a left leaf.%0A     * If so, add the value to sum.%0A     */%0A    public int sumOfLeftLeaves3(TreeNode root) %7B%0A        if (root == null) return 0;%0A        Stack%3CTreeNode%3E stack = new Stack%3C%3E();%0A        stack.push(root);%0A        int sum = 0; // Avoid overflow with long? sum should be within integer range.%0A        while (!stack.isEmpty()) %7B%0A            TreeNode node = stack.pop();%0A            if (node.right != null) %7B%0A                stack.push(node.right);%0A            %7D%0A            if (node.left != null) %7B%0A                if (node.left.left == null && node.left.right == null) %7B%0A                    sum += node.left.val;%0A                %7D%0A                stack.push(node.left);%0A            %7D%0A        %7D%0A        return sum;%0A    %7D%0A%0A    /**%0A     * Level-order traversal or BFS.%0A     */%0A    public int sumOfLeftLeaves4(TreeNode root) %7B%0A        if (root == null) return 0;%0A        int sum = 0;%0A        Queue%3CTreeNode%3E queue = new ArrayDeque%3C%3E();%0A        queue.offer(root);%0A        while (!queue.isEmpty()) %7B%0A            TreeNode node = queue.poll();%0A            if (node.left != null) %7B%0A                queue.offer(node.left);%0A                if (node.left.left == null && node.left.right == null) %7B%0A                    sum += node.left.val;%0A                %7D%0A            %7D%0A            if (node.right != null) %7B%0A                queue.offer(node.right);%0A            %7D%0A        %7D%0A        return sum;%0A    %7D%0A
 %7D
-%0A

update 404. Sum of Left Leaves with more traversals