113. Path Sum II

    /*
     * 113. Path Sum II 
     * 11.18 By Mingyang
     * 典型的backtracking，不过注意，这里的值可能是负数，所以不能用sum小于0来做任何判断
     * 1.长度标准：无
     * 2.可选的范围：每一个node的左边和右边子节点（不为空的情况）。
     * 3.往前走一步：temp加一个，sum减一个
     * 4.后退一步：把temp remove掉
     * 5.特殊的case：root==null也就是走到了根节点的下一个空了
     * 这个题目别看答案简单，自己做起来千疮百孔了：
     * 1.dfs函数以前习惯一上来就是成功案例的base case，殊不知万一root为null的情况根本就没有下文了
     * 2.需要一开始就把temp加上root的值，因为万一遇到只有一个节点1，和sum=1，应该返回new ArrayList<Integer>(temp）
     * 总结就是注意空节点的判断和左右节点分别为空的判断才能走下一步
     */
     public List<List<Integer>> pathSum(TreeNode root, int sum) {
         List<List<Integer>> res = new ArrayList<List<Integer>>();
         List<Integer> temp = new ArrayList<Integer>();
         dfs(root, sum, res, temp);
         return res;
     }
     public void dfs(TreeNode root, int sum, List<List<Integer>> res, List<Integer> temp){
         if(root==null) return;
         temp.add(root.val);
         if(root.left==null && root.right==null ){
             if(root.val==sum)
                 res.add(new ArrayList<Integer>(temp));
             return;
         }
         if(root.left!=null) {
             dfs(root.left,sum-root.val,res,temp);
             temp.remove(temp.size()-1);
         }
         if(root.right!=null) {
             dfs(root.right,sum-root.val,res,temp);
             temp.remove(temp.size()-1);
         }
     }