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.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def dfs(self, node, is_left):
9 if not node:
10 return 0
11 if not node.left and not node.right and is_left:
12 return node.val
13 return self.dfs(node.left, True) + self.dfs(node.right, False)
14
15 def sumOfLeftLeaves(self, root):
16 return self.dfs(root, False)For Python, the recursive method involves a dfs helper that accumulates all the values of left leaves in a tree recursively. The use of a helper function makes it simple to track the 'left' node status.
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#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
int sum = 0;
stack<pair<TreeNode*, bool>> stk;
stk.push({root, false});
while (!stk.empty()) {
TreeNode* node = stk.top().first;
bool isLeft = stk.top().second;
stk.pop();
if (!node->left && !node->right && isLeft) {
sum += node->val;
}
if (node->right) {
stk.push({node->right, false});
}
if (node->left) {
stk.push({node->left, true});
}
}
return sum;
}
};The iterative C++ method represents nodes and their 'left-child' status using a stack. As the nodes traverse the binary tree, any left leaf node's value gets summed up to achieve the final result.