Sponsored
Sponsored
This approach makes use of recursive DFS to traverse from the root to all leaf nodes while maintaining the path number formed by the nodes on the path. At each step, multiply the current number by 10 and add the node's value to propagate the root-to-leaf number down the path. When a leaf node is reached, add the path number to an overall sum.
Time Complexity: O(n), where n is the number of nodes, as it has to visit each node.
Space Complexity: O(h), where h is the height of the tree due to recursive call stack.
1class Solution:
2 def sumNumbers(self, root: TreeNode) -> int:
3 def dfs(node, current_sum):
4 if not node:
5 return 0
6 current_sum = current_sum * 10 + node.val
7 if not node.left and not node.right:
8 return current_sum
9 return dfs(node.left, current_sum) + dfs(node.right, current_sum)
10 return dfs(root, 0)The Python solution utilizes the nested function dfs which traverses the binary tree and calculates the path sums for all root-to-leaf paths using a recursive approach.
This approach uses an iterative DFS with a stack to avoid deep recursive calls. Here, we use a stack to simulate the call stack and iterate through the nodes. Each entry in the stack contains the node and the path sum up to that node, allowing us to process nodes on the path to construct the full number.
Time Complexity: O(n).
Space Complexity: O(n), due to the stack storing all nodes at least once.
1
This C solution uses a manually managed stack to simulate the DFS traversal. Each element in the stack stores the current node and the sum formed up to that node. The approach emulates the process of recursion iteratively.