Another accepted Java solution


  • 11
    public class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            pathSum(root, sum, new ArrayList<Integer>(), res);
            return res;
        }
        
        void pathSum(TreeNode root, int sum, List<Integer> sol, List<List<Integer>> res) {
            if (root == null) {
                return;
            }
            
            sol.add(root.val);
            
            if (root.left == null && root.right == null && sum == root.val) {
                res.add(new ArrayList<Integer>(sol));
            } else {
                pathSum(root.left, sum - root.val, sol, res);
                pathSum(root.right, sum - root.val, sol, res);
            }
            
            sol.remove(sol.size() - 1);
        }
    }

  • 1
    Y

    @jeantimex Thank you for the solution!
    what does the last line of code mean? what do you mean by sol.remove(sol.size() - 1);


  • 1
    I

    @ysun350 Notice that only one copy of the 'sol' list is used. So taking the example given on the problem - while processing the left side, it will add 7 to the original list. Then it processes 7 and because it contains nulls it returns. This 7 then has to be removed before processing 2 on the right side to give correct answer. Not sure if I explain ok.


  • 2
    S

    Re: Another accepted Java solution
    @jeantimex Thank you for your solution !
    I am a fresh man to Java language, and I have a question.
    In your void pathSum(TreeNode root, ...) function, I change the block

    if (root.left == null && root.right == null && sum == root.val ) {
        res.add(new ArrayList<Integer>(sol));
    }
    

    with

    if (root.left == null && root.right == null && sum == root.val ) {
        res.add(sol);
    }
    

    but It didn't work. Would you mind helping to figure it out? Thank you : )


  • 2
    H

    @spencerL when the recursion goes up, the sol size will always decrease by1. As a result, the final size of sol will be 0. So if you write res.add(sol), it will be null list finally. The function of new ArrayList<Integer>(sol) is to create a new list which has same value as sol, rather than res.add(sol) offering the reference to sol. I am not sure whether I explain clearly, free to follow up if you still don't understand.


  • 0
    S

    @hang34 Thank you for your reply. I am sorry to reply so late. On the day when I posted the question I checked reply frequently, and there was no one. So I guessed maybe this questition was too easy to get reply.
    Your reply helps a lot. But I stil have little puzzle. I think sol always contains one element , i.e, the value of root util the program done.
    And res.add(sol) will add the object to which sol points to res, new ArrayList<Integer>(sol) does the same thing except that Adding a new object which is same to sol.
    So I still cannot figure out what is the difference between these two ways? Well, only the latter works.
    Would you please give me some tips? I am new to Java, thank you.


  • 0
    H

    @spencerL you can assume that sol is a box, res add a reference to the box. Let's put it in a easy way, it is like you know the way to a place, in this situation, place is the box, way is the reference. res only adds the way to the place, not the place itself. That is java reference. As for new ArrayList<Integer>(sol), it creates a new array list and instantiates the arraylist using the sol. One is offering the reference, and the other is creating a arraylist.


  • 0
    S

    @hang34 Thank you for your vivid explaination. I got your opinions. However, I am not sure whether add()method of ArrayList actually add the reference of object, or the object itself.
    I checked the Java API doc of this part. It says "Appends the specified element to the end of this list." More details can be seen at https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#add(E)
    I think "appends the specified elements " is ambiguous.
    Thank you for your opinions .


  • 0
    S

    @hang34 I am a noob , and I wanna figure it out whether add()method of ArrayList actually add the reference of object, or the object itself.
    could you please give me some tips? Thank you :)


  • 1
    I

    @spencerL Hi Spencer, the add method will work with the reference of the sol list. Therefore when the sol list's elements are removed, the elements within the res list also change. This should explain the first answer from @hang34

    Also, the object and the object reference are sort of the same thing for an arrayList. ArrayList works on references.

    it would help to read how pass by value and pass by references are different and also how Java implements them. Hopefully this will help.


  • 0
    S

    @iceman28 @hang34 Thank you all guys, I will make up this part.


  • 1

    Hello, my code is basically same as yours
    However, I remove the last element in list after each call of helper function of left child and right child. I don't get why you can remove the last one after two calls of helper. Could you explain a little bit? Thank you!

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

  • 0
    B

    @jessejesse
    Maybe my explanation isn't a good one. But look at your last two if blocks, list.remove(list.size() - 1); will be executed not matter what would be if conditions. That's why you can just keep them at the bottom.


Log in to reply
 

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