113. Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

回溯，每次将root的值添加到list中。并计算新的sum值。分别向左右子节点进行递归，然后回溯。
当节点没有左右子节点，且sum等于targetSum则将新建的list添加到结果中。
（注意这一步内也需要进行回溯操作。）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ret;
    int target;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ret = new ArrayList<>();
        if(root == null) return ret;
        target = targetSum;
        backTrack(root, 0, new ArrayList<>());
        return ret;
    }
    
    private void backTrack(TreeNode root, int sum, List<Integer> nodes){
        if(root.left == null && root.right == null){
            sum += root.val;
            if(sum == target){
                nodes.add(root.val);
                ret.add(new ArrayList<Integer>(nodes));
                nodes.remove(nodes.size()-1);
            }
            return;
        }
        nodes.add(root.val);
        sum += root.val;
        if(root.left != null) backTrack(root.left, sum, nodes);
        if(root.right != null) backTrack(root.right, sum, nodes);
        nodes.remove(nodes.size()-1);
        sum -= root.val;
    }
}