Sponsored
Sponsored
Using a recursive DFS, traverse each path from root to leaf, maintaining the current path and its corresponding sum. When a leaf is reached, check if the path's sum matches the targetSum. Use backtracking to explore all paths.
Time Complexity: O(N), where N is the number of nodes in the tree.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.
1using System.Collections.Generic;
2
3public class TreeNode {
4 public int val;
5 public TreeNode left;
6 public TreeNode right;
7 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
8 this.val = val;
9 this.left = left;
10 this.right = right;
11 }
12}
13
14public class Solution {
15 public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
16 IList<IList<int>> result = new List<IList<int>>();
17 List<int> path = new List<int>();
18 Dfs(root, targetSum, path, result);
19 return result;
20 }
21
22 private void Dfs(TreeNode node, int sum, List<int> path, IList<IList<int>> result) {
23 if (node == null) return;
24 path.Add(node.val);
25 if (node.left == null && node.right == null && sum == node.val) {
26 result.Add(new List<int>(path));
27 } else {
28 Dfs(node.left, sum - node.val, path, result);
29 Dfs(node.right, sum - node.val, path, result);
30 }
31 path.RemoveAt(path.Count - 1);
32 }
33}This C# solution adopts a similar DFS approach with a recursive function, tracking remaining sums and current paths through list operations. Successful paths meeting conditions are added to the result list using backtracking.
An iterative approach using a stack can also be used for this problem. We maintain stacks that parallel traditional DFS traversal with added structures to track path and cumulative sum states for efficient exploration of all feasible root-to-leaf paths.
Time Complexity: O(N), as each node is processed exactly once.
Space Complexity: O(N), since results and stack can store all nodes during worst-case full-tree traversal.
1#include <vector>
2#include <stack>
3using namespace std;
4
5struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
if (!root) return result;
stack<pair<TreeNode*, pair<int, vector<int>>>> stk;
stk.push({root, {root->val, {root->val}}});
while (!stk.empty()) {
auto [node, state] = stk.top(); stk.pop();
auto [currentSum, path] = state;
if (!node->left && !node->right && currentSum == targetSum) {
result.push_back(path);
}
if (node->right) {
path.push_back(node->right->val);
stk.push({node->right, {currentSum + node->right->val, path}});
path.pop_back();
}
if (node->left) {
path.push_back(node->left->val);
stk.push({node->left, {currentSum + node->left->val, path}});
path.pop_back();
}
}
return result;
}
};This C++ solution employs a stack to simulate DFS traversal iteratively. The stack holds node, cumulative sum, and path data. As each node is processed, we check for valid paths and update the result list accordingly. Paths are extended by exploring left and right children, augmented by the current node value.