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.
1function sumNumbers(root) {
2 function dfs(node, currentSum) {
3 if (!node) return 0;
4 currentSum = currentSum * 10 + node.val;
5 if (!node.left && !node.right) return currentSum;
6 return dfs(node.left, currentSum) + dfs(node.right, currentSum);
7 }
8 return dfs(root, 0);
9}In JavaScript, the function dfs is defined within sumNumbers and is used to traverse the tree, summing the path numbers for root-to-leaf paths recursively.
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.
1Python utilizes a list to implement the stack for iterating over nodes. Each tuple in the stack maintains the node and the path sum up to that point.