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.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 void dfs(TreeNode* root, int targetSum, vector<int>& path, vector<vector<int>>& result) {
16 if (!root) return;
17 path.push_back(root->val);
18 targetSum -= root->val;
19 if (!root->left && !root->right && targetSum == 0) {
20 result.push_back(path);
21 } else {
22 dfs(root->left, targetSum, path, result);
23 dfs(root->right, targetSum, path, result);
24 }
25 path.pop_back();
26 }
27 vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
28 vector<vector<int>> result;
29 vector<int> path;
30 dfs(root, targetSum, path, result);
31 return result;
32 }
33};We define a recursive DFS function that traverses each path, checks for a matching sum at leaf nodes, and uses backtracking to remove nodes from the current path before returning to the previous call. This ensures all possible paths are explored.
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.
1function TreeNode(val, left, right) {
2
This JavaScript solution leverages a stack for iterative DFS traversal. Each stack element tracks the node, cumulative sum, and path. When paths qualify as solutions at leaf nodes, they're aggregated into results using path concatenation for subsequent level exploration.