Accepted solution using DFS


  • 0
    N

    import java.util.*;

    public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> ret = new Vector<List<Integer>>();
    if (root == null) {
    return ret;
    }

        List<Integer> curList = new Vector<Integer>();
        int curSum = root.val;
        
        curList.add(root.val);
        
        if (root.left != null)
            getList(root.left, ret, curList, sum, curSum);
        if (root.right != null)
            getList(root.right, ret, curList, sum, curSum);
        if (root.left == null && root.right == null && curSum == sum)
            ret.add(curList);
            
        return ret;
    }
    
    public void getList (TreeNode thisNode, List<List<Integer>> ret, List<Integer> curList, int sum, int curSum) {
    
            curSum += thisNode.val;
            curList.add(thisNode.val);
            
            if (thisNode.left != null)
                getList(thisNode.left, ret, curList, sum, curSum);
                
            if (thisNode.right != null)
                getList(thisNode.right, ret, curList, sum, curSum);
            
            if (thisNode.left == null && thisNode.right == null) {
                if (curSum == sum) {
                    List<Integer> newList = new Vector<Integer>();
                    for (int i = 0; i < curList.size(); i++) {
                        newList.add(curList.get(i));
                    }
                    ret.add(newList);
                }
            
            }
            
    
        
        curList.remove(curList.size() - 1);
    }
    

    }


Log in to reply
 

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