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.
1#include <stdio.h>
2
3int dfs(struct TreeNode* node, int current_sum) {
4 if (node == NULL) return 0;
5 current_sum = current_sum * 10 + node->val;
6 if (node->left == NULL && node->right == NULL) return current_sum;
7 return dfs(node->left, current_sum) + dfs(node->right, current_sum);
8}
9
10int sumNumbers(struct TreeNode* root) {
11 return dfs(root, 0);
12}We use a helper function dfs that recursively computes the sum of the current path number while traversing the tree. If a leaf node is reached, it returns the current computed path sum. Otherwise, it recurses deeper into the tree.
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
In Java, two stacks are utilized: one for nodes and another for maintaining current sum paths similar to call stack operations in recursive DFS.