Simplest java DFS bottom up solution

  • 0

    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) {
                // If a leaf node equal to the reduced sum, create new linked list and add leaf
                List<Integer> path = new LinkedList<>();
            // 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++) {

Log in to reply

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