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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public int Dfs(TreeNode node, bool isLeft) {
10 if (node == null) return 0;
11 if (node.left == null && node.right == null && isLeft) return node.val;
12 return Dfs(node.left, true) + Dfs(node.right, false);
13 }
14 public int SumOfLeftLeaves(TreeNode root) {
15 return Dfs(root, false);
16 }
17}In C#, the recursive DFS is implemented in a similar manner. A helper method Dfs is crafted to traverse the binary tree and sum up the values of all left leaves.
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.