Given the root of a binary tree, return the sum of all left leaves.
A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.
Example 2:
Input: root = [1]
Output: 0
Constraints:
The number of nodes in the tree is in the range [1, 1000].
-1000 <= Node.val <= 1000
My Solution
We can do this with a helper function that takes two arguments - the current TreeNode and a boolean variable that indicates whether or not the current node is the left child of another node. If the current node is null, we return 0. If the current node is a leaf node and it is the left child of another node we return the value of that node. Otherwise we add the sums of the left and right subtrees, passing in the boolean variable indicating whether the node is a left or right child accordingly.
Time complexity is O(n) since we visit all the nodes. Space complexity is O(log n) due to the space required on the call stack since we are making recursive calls.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return helper(root, false);
}
public int helper(TreeNode root, boolean left) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null && left) {
return root.val;
}
return helper(root.left, true) + helper(root.right, false);
}
}