这题说的是找出所有路径和为 target 的路径，这里的路径只能从根节点到叶子节点，这题和上一题类似：《二叉树中和为某一值的路径》。
我们从根节点开始往下累加路径上的节点值，并且还要记录这条路径上的节点，到叶子节点的时候如果累加的值等于 target ，说明这条路径就是我们找的，保存这条路径。
我们使用的是 List （Java语言使用的是List，C++使用的是Vector）来存储路径上的节点，因为它是引用传递，所以递归往下走的时候我们选择节点，递归往回走的时候要撤销选择。
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
dfs(root, target, 0, new ArrayList<>(), ans);
return ans;
}
/**
* @param node 当前节点
* @param target
* @param sum 从根节点到当前节点路径上的和
* @param path 记录从根节点到当前节点路径上的节点值。
* @param ans 返回的结果集。
*/
public void dfs(TreeNode node, int target, int sum, List<Integer> path,
List<ArrayList<Integer>> ans) {
if (node == null)
return;
path.add(node.val);// 记录该路径上的节点
sum += node.val;// 累加从根节点到当前节点这条路径上所有节点的和。
// 如果到达叶子节点，就不能往下走了，直接return
if (node.left == null && node.right == null) {
// 如果到达叶子节点，并且sum等于toal，说明我们找到了一组，
// 要把它放到ans中
if (target == sum)
ans.add(new ArrayList<>(path));
} else {
dfs(node.left, target, sum, path, ans);// 递归到左子节点
dfs(node.right, target, sum, path, ans);// 递归到右子节点
}
path.remove(path.size() - 1);// 往回走撤销选择
}
public:
vector<vector<int>> FindPath(TreeNode *root, int target) {
vector<vector<int>> ans;
vector<int> path;
dfs(root, target, 0, path, ans);
return ans;
}
/**
* @param node 当前节点
* @param target
* @param sum 从根节点到当前节点路径上的和
* @param path 记录从根节点到当前节点路径上的节点值。
* @param ans 返回的结果集。
*/
void dfs(TreeNode *node, int target, int sum, vector<int> &path,
vector<vector<int>> &ans) {
if (node == nullptr)
return;
path.push_back(node->val);// 记录该路径上的节点
sum += node->val;// 累加从根节点到当前节点这条路径上所有节点的和。
// 如果到达叶子节点，就不能往下走了，直接return
if (node->left == nullptr && node->right == nullptr) {
// 如果到达叶子节点，并且sum等于toal，说明我们找到了一组，
// 要把它放到ans中
if (target == sum)
ans.push_back(path);
} else {
dfs(node->left, target, sum, path, ans);// 递归到左子节点
dfs(node->right, target, sum, path, ans);// 递归到右子节点
}
path.pop_back();// 往回走撤销选择
}
京公网安备 11010502036488号