Sum of Left Leaves
Problem
Given the root of a binary tree, return the sum of all left leaves. A left leaf is a leaf that is the left child of its parent.
root = [3,9,20,null,null,15,7]24def sum_of_left_leaves(root):
def dfs(node, is_left):
if not node: return 0
if not node.left and not node.right:
return node.val if is_left else 0
return dfs(node.left, True) + dfs(node.right, False)
return dfs(root, False)function sumOfLeftLeaves(root) {
function dfs(node, isLeft) {
if (!node) return 0;
if (!node.left && !node.right) return isLeft ? node.val : 0;
return dfs(node.left, true) + dfs(node.right, false);
}
return dfs(root, false);
}class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return dfs(root, false);
}
int dfs(TreeNode n, boolean isLeft) {
if (n == null) return 0;
if (n.left == null && n.right == null) return isLeft ? n.val : 0;
return dfs(n.left, true) + dfs(n.right, false);
}
}class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) { return dfs(root, false); }
int dfs(TreeNode* n, bool isLeft) {
if (!n) return 0;
if (!n->left && !n->right) return isLeft ? n->val : 0;
return dfs(n->left, true) + dfs(n->right, false);
}
};Explanation
We only want to add up the left leaves — leaves that happen to be a left child. The tricky part is that a node alone cannot tell whether it is a left or right child, so we carry that fact down as we recurse.
The helper dfs(node, is_left) takes a second flag saying whether this node was reached by going left from its parent. We start at the root with is_left = False, because the root is nobody's left child.
At each node, if it is a leaf (no left and no right child), we return its value only when is_left is true, otherwise 0. For an internal node, we recurse left with the flag set to True and recurse right with False, then add the two results.
Example: [3,9,20,null,null,15,7]. Node 9 is a leaf reached by going left, so it counts. Node 15 is also a left-child leaf, so it counts. Node 7 is a right leaf and is ignored. Total = 9 + 15 = 24.
Every node is visited once, so the runtime is O(n).