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 class Solution {
    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.