二叉树中和为某一值的路径(二)

 

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();

}

}