Binary tree - 404. Sum of left leaves

1 Title Description

Given the root node of a binary tree root , Returns the sum of all left leaves .

2 Title Example

Example 2:

Input : root = [1]
Output : 0

3 Topic tips

The number of nodes is [1, 1000] Within the scope of
-1000 <= Node.val <= 1000

4 Ideas

A node is 「 Left leaf 」 node , If and only if it is the left child of a node , And it's a leaf node . So we can consider traversing the whole tree , When we traverse to the node node when , If its left child node is a leaf node , Then add up the values of its left child nodes into the answer .
depth ：
Complexity analysis

• Time complexity :o(n), among n Is the number of nodes in the tree .
• Spatial complexity :O(n). Spatial complexity is related to the maximum depth of the stack used by depth first search . In the worst case , The tree presents a chain structure , Depth is O(n), The corresponding spatial complexity is also O(n).
  Breadth ：
  Complexity analysis
• Time complexity :O(n), among n Is the number of nodes in the tree .
• Spatial complexity :O(n). The spatial complexity is related to the capacity of the queue used by breadth first search , by O(n).

recursive ：
The traversal order of recursion is post order traversal ( Right and left ), It is because the sum of the left leaf values is accumulated through the return value of the recursive function ..
Recursive Trilogy :

1. Determine the parameters and return values of recursive functions
   A node and a leaf of the tree , Then you must pass in the root node of the tree , The return value of a recursive function is the sum of numeric values , So for int
   Just use the function given in the title .

2. Determine termination conditions
   Is still

   if (root NLLL) return O ;
   

3. Determine the logic of monolayer recursion
   When you encounter the left leaf node , Record the values , Then the sum of the left leaves of the left subtree is obtained recursively , And the sum of the left leaves of the right subtree , The sum is the sum of the left leaves of the whole tree .

5 My answer

depth ：

class Solution {
    
    public int sumOfLeftLeaves(TreeNode root) {
    
        return root != null ? dfs(root) : 0;
    }

    public int dfs(TreeNode node) {
    
        int ans = 0;
        if (node.left != null) {
    
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        if (node.right != null && !isLeafNode(node.right)) {
    
            ans += dfs(node.right);
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
    
        return node.left == null && node.right == null;
    }
}

Breadth ：

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

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
    
            TreeNode node = queue.poll();
            if (node.left != null) {
    
                if (isLeafNode(node.left)) {
    
                    ans += node.left.val;
                } else {
    
                    queue.offer(node.left);
                }
            }
            if (node.right != null) {
    
                if (!isLeafNode(node.right)) {
    
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
    
        return node.left == null && node.right == null;
    }
}

Normal recursion ：

class Solution {
    
    public int sumOfLeftLeaves(TreeNode root) {
    
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    //  Left 
        int rightValue = sumOfLeftLeaves(root.right);  //  Right 
                                                       
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
     //  in 
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
}