题目

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

思路

使用前序遍历，并统计当前路径的sum。
当某个节点已经不在路径内，需要回溯，将这个节点出栈，并从sum中减去对应的值。

实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
        List<List<Integer>> res = new ArrayList<>();

        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<Integer> path = new ArrayList<>();
            dfs(root, sum, path);
            return res;
        }
        
        public void dfs(TreeNode root, int sum, List<Integer> path){
            
            if(root==null) return;

            path.add(root.val);
            
            if(root.left==null && root.right==null )
                if(root.val==sum)
                    res.add(new ArrayList<Integer>(path));
            
            if(root.left!=null) 
                dfs(root.left,sum-root.val,path);
            
            if(root.right!=null) 
                dfs(root.right,sum-root.val,path);
            
            path.remove(path.size()-1);
            
        }
}