NC8 二叉树根节点到叶子节点和为指定值的路径

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    ArrayList<Integer> path = new ArrayList<Integer>();
    ArrayList<ArrayList<Integer>> res =new ArrayList<ArrayList<Integer>>(); 
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        dfs(root,0,sum);
        return res;
    }

    public void dfs(TreeNode root,int cursum,int target){
        if(root == null) return;
        cursum += root.val;

        path.add(root.val);

        if(root.left == null && root.right == null){
            if(cursum == target)
                res.add(new ArrayList(path));
        }else{
            //这里不知道为什么 先 right 后 left 最后一个用例过不去
            dfs(root.left,cursum,target);
            dfs(root.right,cursum,target);
        }


        path.remove(path.size()-1);
    }
}

temp 数组 每次添加的时候为了污染
使用 res.add(new ArrayList(temp))

递归程序为 void ， 变量保存在 传入的参数当中。

每次遍历可以记录路径 也可以计算total， 我当时想的是返回的时候确认 total ==sum 再返回记录当前的值。 有点费劲。 还是一边遍历 一边记录好。
遍历到最后一个 temp需要去除 temp记录的是当前路径

当传入参数为int类型等 这个值并不会根据后面递归的变化而改变 例如 total 即使经过左节点的递归之后 total在右节点递归时 还是 开始的值
但是传入 链表 数组等这种地址时 其中 的值会随着递归改变 所有需要在递归完当前节点后将temp最后一个删除。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        psum(root, 0,sum, new ArrayList<>(), result);
        return result;
    }

    public void psum(TreeNode root, int total, int sum, ArrayList<Integer> temp, List<ArrayList<Integer>> res){
        if(root == null) return;

        total = total + root.val;
        temp.add(new Integer(root.val));
        if(root.left == null && root.right == null){
            if(total == sum){
                res.add(new ArrayList(temp)); // 新的
            }
            temp.remove(temp.size() - 1);

            return;
        }


        psum(root.left, total, sum, temp, res);
        psum(root.right, total, sum, temp, res);
        temp.remove(temp.size() - 1);
    }

}