剑指offer：二叉树中和为某一值的路径（回溯）

题目

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例

给定如下二叉树，以及目标和 sum = 22

返回：
[ [5,4,11,2], [5,8,4,5] ]

代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
    
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(root, sum, result, list);
        return result;
    }
    public void dfs(TreeNode root, int target, List<List<Integer>> result, List<Integer> list){
    
        if(root == null){
    
            return;
        }
        list.add(root.val);
        target = target - root.val;
        if(target == 0 && root.left == null && root.right == null){
    
            List<Integer> temp = new ArrayList<>();
            for(Integer val : list){
    
                temp.add(val);
            }
            result.add(temp);
        }else{
    
            dfs(root.left, target, result, list);
            dfs(root.right, target, result, list);
        }
        list.remove(list.size()-1);

    }
}