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 {
2public:
3 int dfs(TreeNode* node, int current_sum) {
4 if (!node) return 0;
5 current_sum = current_sum * 10 + node->val;
6 if (!node->left && !node->right) return current_sum;
7 return dfs(node->left, current_sum) + dfs(node->right, current_sum);
8 }
9
10 int sumNumbers(TreeNode* root) {
11 return dfs(root, 0);
12 }
13};The C++ solution mirrors that of C. The dfs function is used to accumulate the path number and generates the total sum for root-to-leaf paths.
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.