二叉树中和为某一值的路径
题目描述
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例：
给定如下二叉树，以及目标和 sum = 22，
image
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示：
题目分析
开门见山不叭叭：回溯加深搜
- 从根节点开始，使用一个nowPath记录当前已走路径，使用一个nowSum记录当前路径总和
- 判断当前节点是不是叶子节点
2.1 如果当前节点是叶子节点，判断当前路径总和是否等于sum，若等于，将{nowPath + 当前节点}加入到result里，若不等，返回
2.2 如果当前节点不是叶子节点，将当前节点加入到nowPath，同时更新nowSum，并继续DFS - 当前节点的左右子树都遍历完毕之后，回溯，将当前节点从nowPath里移除，更新nowSum，返回
- 返回result
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
search(root,sum,0,new ArrayList<Integer>());
return result;
}
public void search(TreeNode root,int sum,int nowSum,List<Integer> nowPath){
if(root == null) return;
if(root.left == null
&& root.right == null
&& nowSum + root.val == sum){
nowPath.add(root.val);
List<Integer> tmp = new ArrayList<>(nowPath);
result.add(tmp);
nowPath.remove(nowPath.size() - 1);
return;
}
nowPath.add((Integer)root.val);
search(root.left,sum,nowSum + root.val,nowPath);
search(root.right,sum,nowSum + root.val,nowPath);
nowPath.remove(nowPath.size() - 1);
}
