LeetCode-113-路径总和II

1. 一眼回溯，如果大于则倒退，等于的话记录且倒退，小于则继续加。
2. 忽略了一点是有可能出现负数，所以直接找到底即可，不用判断是否大于或小于。

    //最终返回
    List> ans = new ArrayList<>();
    public List> pathSum(TreeNode root, int targetSum) {
        //root能否加入进去
        if(root==null) return ans;
        //如果可以加入 进入回溯
        List ll = new ArrayList<>();
        ll.add(root.val);
        if(root.left==null && root.right==null){
            if(root.val==targetSum){
                ans.add(ll);
            }
            return ans;
        }
        if(root.left!=null) back(root.left,targetSum,root.val,ll);
        if(root.right!=null) back(root.right,targetSum,root.val,ll);
        return ans;
    }

    //现在进入的是root 目标是targetSum 现在的和是nowSum 现在的列表是now_list
    //需要注意 就算目前的和大于targetSum 后面有可能出现负数 所以也必须找下去
    public void back(TreeNode root,int targetSum,int nowSum,List now_list){
        if(root.left==null && root.right==null){ // 如果是叶子节点
            if(root.val+nowSum==targetSum){ //相等且加入
                now_list.add(root.val);
                ans.add(new ArrayList<>(now_list));
                now_list.remove(now_list.size()-1);
            }
        }else { //如果不是叶子节点 加入且遍历
            now_list.add(root.val);
            if(root.left!=null) back(root.left,targetSum,nowSum+root.val,now_list);
            if(root.right!=null) back(root.right,targetSum,nowSum+root.val,now_list);
            //移出
            now_list.remove(now_list.size()-1);
        }
        return;
    }