剑指 Offer 34. 二叉树中和为某一值的路径

 这题第一反应就是递归，然后虽然磕磕绊绊做出来了，但是时间复杂度惨得要死

 思路如下：

 总的思路就是递归，另外注意如果没有结果返回是空数组，这样也符合递归函数最终的返回值意义

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null)
        {return result;}
        if(root.left==null&&root.right==null)
        {
            if(root.val==sum)
            {
                List list=new ArrayList<>();
                list.add(root.val);
                result.add(list);
                return result;
            }
            else
            {return new ArrayList<>();}   
        }
        
        List<List<Integer>> resultLeft=new ArrayList<>();;
        List<List<Integer>> resultRight=new ArrayList<>();;
        if(root.left!=null)
        {
            resultLeft=pathSum(root.left,sum-root.val);
            if(resultLeft.size()!=0)
            {
                for(List<Integer> list:resultLeft)
                {list.add(0,root.val);}//这里修改了Resultleft的值吗
            }
        }

        if(root.right!=null)
        {
            resultRight=pathSum(root.right,sum-root.val);
            if(resultRight.size()!=0)
            {
                for(List<Integer> list:resultRight)
                {list.add(0,root.val);}//这里修改了Resultleft的值吗
            }
        }

        if(resultRight.size()==0&&resultLeft.size()==0)
        {return new ArrayList<>();}
        else if(resultLeft.size()==0)
        {return resultRight;}
        else if(resultRight.size()==0)
        {return resultLeft;}
        else 
        {
            resultLeft.addAll(resultRight);
            return resultLeft;
        } 
    }
}

相比起来，这种递归的方式更好，因为其中直接在去往叶子节点的路上就建好了list

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, sum, new ArrayList<>(), result);
    return result;
}

public void dfs(TreeNode root, int sum, List<Integer> list,
                List<List<Integer>> result) {
    //如果节点为空直接返回
    if (root == null)
        return;
    //因为list是引用传递，为了防止递归的时候分支污染，我们要在每个路径
    //中都要新建一个subList
    List<Integer> subList = new ArrayList<>(list);
    //把当前节点值加入到subList中
    subList.add(new Integer(root.val));
    //如果到达叶子节点，就不能往下走了，直接return
    if (root.left == null && root.right == null) {
        //如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
        //要把它放到result中
        if (sum == root.val)
            result.add(subList);
        //到叶子节点之后直接返回，因为在往下就走不动了
        return;
    }
    //如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
    //下一步的时候，sum值要减去当前节点的值
    dfs(root.left, sum - root.val, subList, result);
    dfs(root.right, sum - root.val, subList, result);
}

https://zhuanlan.zhihu.com/p/112926891