题解 | #二叉树根节点到叶子节点和为指定值的路径#

借鉴了牛客讨论区和Leetcode的题解。加了注释方便理解

 public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        if(root==null) return res;
        Deque<Integer> path=new ArrayDeque<>();   //jdk建议这样实现栈 ，双向队列
        dfs(root,sum,path,0,res);                //源头开始dfs搜索
        return res;
    }

    //深度优先搜索
    public void dfs(TreeNode root,int sum,Deque<Integer> path,
                    int total,ArrayList<ArrayList<Integer>> res){
        if(root==null) return ;
        path.addLast(root.val);    //把当前节点值加入 队列中
        total+=root.val;           //计算每条路径的总和
        if(root.left==null &&root.right==null){   //这里表示已经到达叶子节点
            if(sum==total) res.add(new ArrayList<>(path));
            path.removeLast();     // 回溯，寻找下一个 符合的
            return;                //避免进入下面的查找
        }
        //跳过了上面的说明，还未到达叶子节点，继续查找
        dfs(root.left,sum,path,total,res);
        dfs(root.right,sum,path,total,res);
        //回溯 ，上面的是if判断，和这里的不同
        path.removeLast();
    }