Algorithm
Problem Name: 404. Sum of Left Leaves
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
void sumleft(struct TreeNode *node, int *n, int left) {
if (!node) return;
sumleft(node->left, n, 1);
if (left && !node->left && !node->right) *n += node->val;
sumleft(node->right, n, 0);
}
int sumOfLeftLeaves(struct TreeNode* root) {
int n = 0;
sumleft(root, &n, 0);
return n;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
// Recursive
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
return !root ? 0 : (root->left && !root->left->left && !root->left->right ? root->left->val : 0) +
sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};
// Iterative
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(!root) return 0;
stack < TreeNode*>s;
int sum = 0;
while(!s.empty() || root){
while(root){
s.push(root);
root = root->left;
if(root && !root->left && !root->right) sum += root->val;
}
root = s.top()->right;
s.pop();
}
return sum;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int sum = 0;
Queue < TreeNode[]> queue = new LinkedList<>();
queue.add(new TreeNode[]{root, null});
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode[] removed = queue.remove();
TreeNode node = removed[0];
TreeNode parent = removed[1];
if (node.left == null && node.right == null) {
if (parent != null && parent.left == node) {
sum += node.val;
}
} else {
if (node.left != null) {
queue.add(new TreeNode[]{node.left, node});
}
if (node.right != null) {
queue.add(new TreeNode[]{node.right, node});
}
}
}
}
return sum;
}
}
Input
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const sumOfLeftLeaves = function(root) {
if(root == null) return 0
let res = 0
function dfs(node, side) {
if(node === null) return
if(node.left === null && node.right === null) {
if(side === 'left') res += node.val
return
}
dfs(node.left, 'left')
dfs(node.right, 'right')
}
dfs(root.left, 'left')
dfs(root.right, 'right')
return res
};
Input
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def left(node, sm):
if not node: return
left(node.left,sm)
if node.left:
if not node.left.left and not node.left.right: sm.append(node.left.val)
left(node.right,sm)
otp=list()
left(root,otp)
return sum(otp)
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0404_SumOfLeftLeaves
{
public int SumOfLeftLeaves(TreeNode root)
{
return Compute(root, false);
}
private int Compute(TreeNode node, bool left)
{
if (node == null) return 0;
if (node.left == null && node.right == null)
return left ? node.val : 0;
return Compute(node.left, true) + Compute(node.right, false);
}
}
}
Input
Output