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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10int dfs(struct TreeNode* node, int isLeft) {
11 if (node == NULL) return 0;
12 if (node->left == NULL && node->right == NULL && isLeft) return node->val;
13 return dfs(node->left, 1) + dfs(node->right, 0);
14}
15
16int sumOfLeftLeaves(struct TreeNode* root) {
17 return dfs(root, 0);
18}We define a helper function dfs which takes a node and a boolean indicating whether it is a left child. If the node is a leaf and is a left child, we add its value to the sum. Otherwise, recurse into the left and right subtrees.
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.
1import
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.