404 Sum of Left Leaves
Find the sum of all left leaves in a given binary tree.
Example:
3
/ \
9 20
/ \
15 7
There are two left leaves in the binary tree, with values
9
and
15
respectively. Return
24
.
Complexity: O(N) time and space The Idea: Use any kind of traversal and keep track when you are on a left or right branch.
int sumOfLeftLeaves(TreeNode* root) {
int sum = 0;
preOrderLeftLeafAcc(root, sum, false);
return sum;
}
void preOrderLeftLeafAcc(TreeNode* root, int &sum, bool isLeft) {
if (root) {
if (!root->left && !root->right && isLeft) {
sum += root->val;
}
preOrderLeftLeafAcc(root->left, sum, true);
preOrderLeftLeafAcc(root->right, sum, false);
}
}
Last modified 4yr ago