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 <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 int dfs(TreeNode* node, bool isLeft) {
14 if (!node) return 0;
15 if (!node->left && !node->right && isLeft) return node->val;
16 return dfs(node->left, true) + dfs(node->right, false);
17 }
18 int sumOfLeftLeaves(TreeNode* root) {
19 return dfs(root, false);
20 }
21};In C++, we define a class Solution and use a similar recursive approach. The dfs helper function handles the logic of summing left leaf nodes by traversing the tree recursively.
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
The iterative approach leverages a stack to simulate recursion iteratively in Python. Nodes are pushed onto a stack with information on whether they are left children. Left leaf nodes values are accumulated forming the result.