Simplest java DFS bottom up solution


  • 0
    N

    I tried to avoid using class variables or excessive parameters for helper functions. Building the path bottom up seems to be a good idea, since we will only know if a path is required once we reach a leaf. Hence,

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
            // Create list once
            List<List<Integer>> list = new LinkedList<>();
            sum(root, sum, list);
            return list;
        }
        
        private void sum(TreeNode root, int sum, List<List<Integer>> list) {
            if (root==null) return;
            if (root.right==null && root.left==null) {
                if (root.val!=sum) {
                    return;
                }
                // If a leaf node equal to the reduced sum, create new linked list and add leaf
                List<Integer> path = new LinkedList<>();
                path.add(root.val);
                list.add(path);
                return;
            }
            // get size of list before recursion, any item in the list at this point must not be modified
            int size=list.size();
            sum(root.left, sum-root.val,list);
            sum(root.right, sum-root.val,list);
            // modify the list size onwards after recursion
            for(int i=size; i<list.size(); i++) {
                list.get(i).add(0,root.val);
            }
        }
    

Log in to reply
 

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