AcWing 47. 二叉树中和为某一值的路径
原题链接
中等
作者:
STU756
,
2020-09-01 13:34:16
,
所有人可见
,
阅读 442
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> findPath(TreeNode root, int sum) {
if(root == null || sum == 0) return ans;
help(root, sum , new ArrayList<Integer>());
return ans;
}
//回溯
private void help(TreeNode node, int target, List<Integer> list) {
if(node == null) return;//终止条件
//选择
list.add(node.val);
target -= node.val;
if(target == 0 && node.left == null && node.right == null) {
//找到一个结果
ans.add(new ArrayList<>(list));
}else {
//drill down下一层
help(node.left, target, list);
help(node.right, target, list);
}
//撤销
list.remove(list.size() - 1);
}