Leetcode P113 Java使用DFS解决

执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户

内存消耗：41.1 MB, 在所有 Java 提交中击败了99.83%的用户

首先做一些剪枝操作，如果当前节点为null，就return

        if (root == null){
            return;
        }

接下来我们每次遍历一个节点的时候就 targetSum -= root.val;，当我们遍历到叶子节点的时候比关切targerSum == 0的时候那么这些数据就是我们想要的数据，

        targetSum -= root.val;
        tmp.add(root.val);
        if (targetSum == 0 && root.left == null && root.right == null){
            res.add(new ArrayList<>(tmp));
        }

class Solution {
    List> res = new ArrayList<>();
    public List> pathSum(TreeNode root, int targetSum) {
        ArrayList arrayList = new ArrayList<>();
        dfs(root,targetSum,arrayList);
        return res;
    }

    public void dfs(TreeNode root,int targetSum,List tmp){
        if (root == null){
            return;
        }

        targetSum -= root.val;
        tmp.add(root.val);
        if (targetSum == 0 && root.left == null && root.right == null){
            res.add(new ArrayList<>(tmp));
        }

        dfs(root.left,targetSum,tmp);
        dfs(root.right,targetSum,tmp);
        tmp.remove(tmp.size()-1);
    }
}