Path Sum I I Algorithm
The Path Sum II Algorithm is a popular tree traversal algorithm that is primarily used to find all the root-to-leaf paths in a binary tree where each path's sum equals a given target value. In this algorithm, recursive depth-first search (DFS) is typically employed to traverse through the tree, exploring all possible routes from the root node to the leaf nodes. During the traversal, a running sum is maintained, and upon reaching the leaf nodes, it is checked whether the sum equals the target value. If it does, the path is recorded as a valid path.
A key aspect of the Path Sum II Algorithm is the use of backtracking. Once a leaf node is reached, and the path is checked for validity, the algorithm backtracks to explore other potential paths. This backtracking process involves removing the last visited node from the current path and decrementing the running sum before proceeding with the traversal. By employing this technique, the algorithm ensures that all possible root-to-leaf paths are explored, and their corresponding sums are checked against the target value. As a result, the Path Sum II Algorithm is an efficient and reliable approach to solving the path-sum-related problems in binary trees.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > pathSum(TreeNode *root, int sum) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>> result;
vector<int> path;
dfs(root, 0, sum, path, result);
return move(result);
}
void dfs(TreeNode *node, int value, int sum,
vector<int>& path, vector<vector<int>>& result) {
if (node == NULL) return;
path.push_back(node->val);
if (node->left == NULL && node->right == NULL) {
if (node->val + value == sum) {
result.push_back(path);
}
path.pop_back();
return;
}
if (node->left)
dfs(node->left, node->val + value, sum, path, result);
if (node->right)
dfs(node->right, node->val + value, sum, path, result);
path.pop_back();
}
};
