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.
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.