二叉树中和为某一值的路径(二)
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
//初始化集合
ArrayList res = new ArrayList<>();
LinkedList path = new LinkedList<>();
public ArrayList FindPath(TreeNode root, int target) {
dfs(root, target);
return res;
}
public void dfs(TreeNode root, int tar) {
if (root == null) {
return;
}
//将root节点放入路径集合
path.add(root.val);
//更新目标值，每放入一个节点，目标值应该相应减去对应节点的值，直到目标值为0
tar -= root.val;
//如果目标值减到了0 && 左节点为空 && 右节点为空 证明树已遍历完，此路径为目标路径
if (tar == 0 && root.left == null && root.right == null) {
res.add(new ArrayList(path));
}
// 递归左右子树
dfs(root.left, tar);
dfs(root.right, tar);
//删除当前节点，在回溯过程中，此节点不在新路径上
path.removeLast();
}
}