Sponsored
Sponsored
This approach involves using recursive DFS to traverse the tree. At each node, determine if it is a left leaf. If it is, add its value to the sum and recursively continue to search for more left leaves in the subtree.
The time complexity is O(n) where n is the number of nodes, as we visit each node once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var dfs = function(node, isLeft) {
7 if (node === null) return 0;
8 if (node.left === null && node.right === null && isLeft) return node.val;
9 return dfs(node.left, true) + dfs(node.right, false);
10};
11
12var sumOfLeftLeaves = function(root) {
13 return dfs(root, false);
14};In JavaScript, the code follows a similar structure where a helper function dfs is employed to explore the tree nodes. This function checks for left leaves and sums their values iteratively.
This approach applies iterative DFS using a stack. By exploring each node iteratively, it checks if a node qualifies as a left leaf and accumulates its value to the sum. It manages to mimic a recursive pattern iteratively.
The time complexity is O(n) for navigating each tree node once. Space complexity is O(n) due to maintaining a stack proportional to the number of nodes.
1
In Java, an iterative DFS is achieved through a stack where each node's left child status is managed through pairs. Iteratively visiting each node allows collecting values of left leaves effectively.