DFS in java-easy to understand


  • 0
    U

    use the depth first search, don't forget to reset the solution list once it fit the requirement

        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root ==null) {
                return res;
            }
            DFS(root , sum , res , new ArrayList<Integer>());
            return res;
        }
        private void DFS(TreeNode root , int sum , List<List<Integer>> res, List<Integer> sol) {
            if(root.right == null && root.left == null) {
                if(root.val == sum) {
                    sol.add(root.val);
                    res.add(new ArrayList<Integer>(sol));
                    sol.remove(sol.size() - 1);
                }
                return;
            }
            sum -= root.val;
            if(root.left !=null) {
                sol.add(root.val);
                DFS(root.left, sum , res, sol);
                sol.remove(sol.size() - 1);
            }
            if(root.right != null) {
                sol.add(root.val);
                DFS(root.right,sum,res,sol);
                sol.remove(sol.size() - 1);
            }
            
        }
    }```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.