
Problem Statement
The task involves identifying a specific type of node, known as a left leaf, in a binary tree and computing their cumulative value. For clarity, a leaf in the context of binary trees is a node that does not have any children. More specifically, a left leaf is classified as any leaf that acts as the left child of its parent node. Given the root
node of a binary tree, the objective is to return the sum of values of all these left leaves.
Examples
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
Approach and Intuition
To solve the problem of finding and summing all left leaves in a binary tree, you can apply either iterative or recursive strategies. Given the nature of tree traversals, a recursive approach can be inherently more intuitive. Here’s a basic plan using recursion:
- Start from the root and initiate a sum that keeps track of the values of left leaves.
- For each node, determine if it has a left child which is a leaf:
- Check if the left child exists and if it does not have further children (i.e., both its left and right children are
null
). - If it is a left leaf, add its value to the sum.
- Check if the left child exists and if it does not have further children (i.e., both its left and right children are
- Recursively repeat the process for both left and right children of the current node.
- Terminate the recursion when a
null
node is encountered, which is a base case returning zero (as there's nothing to sum).
In this approach, each node of the tree is visited exactly once, thereby ensuring an O(n) complexity where n is the number of nodes in the tree. This is efficient given the constraints. This method keeps the overhead low and works well within provided constraints (node values between -1000 and 1000, and up to 1000 nodes).
Examples provided demonstrate both cases with multiple left leaves and a simple tree with no leaves, helping illustrate how the sum dynamically accumulates based on tree structure.
Solutions
- Java
class Solution {
public int calculateLeftLeavesSum(TreeNode root) {
int sum = 0;
TreeNode current = root;
while (current != null) {
if (current.left == null) {
current = current.right;
} else {
TreeNode temp = current.left;
if (temp.left == null && temp.right == null) {
sum += temp.val;
}
while (temp.right != null && temp.right != current) {
temp = temp.right;
}
if (temp.right == null) {
temp.right = current;
current = current.left;
} else {
temp.right = null;
current = current.right;
}
}
}
return sum;
}
}
The provided Java program defines a method calculateLeftLeavesSum
designed to calculate the sum of the left leaves in a binary tree. This method uses an iterative traversal approach to navigate through the tree, leveraging a modified version of the Morris traversal technique which avoids the need for additional memory for stack or recursion.
Here's how the method works:
- Initialize a variable
sum
to zero to keep track of the cumulative sum of the leaf values. - Start traversing the binary tree from the root node using a
current
pointer. - Utilize a while loop to process nodes until there are no more nodes to process (
current
becomes null). - Within the loop, check if the left child of the current node does not exist:
- If true, move to the right child of the current node.
- Otherwise, process the left subtree of the node.
- If the left child of the current node itself has no children, it is a left leaf:
- Add its value to
sum
.
- Add its value to
- Check if the rightmost child of the left subtree has been visited by looking at a temporary
temp
that navigates through the right children.- If
temp.right
is null, it means this subtree hasn’t been fully explored:- Make
temp.right
point to the current node for a return path and then movecurrent
to its left child.
- Make
- If
temp.right
is not null, it means returning after the left subtree is fully explored:- Set
temp.right
back to null to restore the original tree structure and movecurrent
to its right child.
- Set
- If
The method continuously updates the sum
whenever a left leaf is found, finally returning the sum
after the tree is fully traversed. This solution is efficient as it avoids using extra space for recursion or a stack, making it suitable for large trees.
- C
int calculateLeftLeafSum(struct TreeNode* root) {
int total = 0;
while (root) {
if (!root->left) {
root = root->right;
} else {
struct TreeNode* precursor = root->left;
if (precursor->left == NULL && precursor->right == NULL) total += precursor->val;
while (precursor->right && precursor->right != root) precursor = precursor->right;
if (!precursor->right) {
precursor->right = root;
root = root->left;
} else {
precursor->right = NULL;
root = root->right;
}
}
}
return total;
}
The provided C code implements a function to calculate the sum of left leaves in a binary tree. This function, calculateLeftLeafSum
, uses a non-recursive approach to traverse the tree, ensuring efficient memory usage.
- The function is initialized with a
total
set to 0 to hold the sum of left leaf values. - It checks each node starting from the root using a
while
loop. - If the current node does not have a left child, traversal moves to the right child.
- If a left child exists, the program checks if it is a leaf (i.e., it does not have its own children). If it is a leaf, its value is added to
total
. - For non-leaf left children, a "predecessor" finder loop ensures each node's left subtree is fully explored before moving back to the right subtree. This involves temporarily modifying the tree structure by making right children of discovered nodes point back to the current node. This technique avoids the use of a parent pointer or a stack.
- After a subtree is processed, the temporary pointers are reverted to restore the tree structure, and the next right child is processed.
This code effectively finds and sums the values of all left leaves in the binary tree without using additional space for recursion or a stack, which is a common challenge in similar tree problems.
No comments yet.