129. Sum Root to Leaf Numbers 这道题有两行代码不是很懂

可以请大神讲解一下，为什么31和32行这里，不能用list而是要重新建list吗？是因为overwrite了吗？如果是的话，在recursion当中为什么会出现overwrite的情况呢？谢谢！

补充内容 (2020-9-10 22:00):
已解决，谢谢大神们！~

楼主你的这种写法看起来还是有点别扭的。
31、32行的这个左右子树的dfs其实也是backtracking的一种特殊形式。对于backtracking，一般的写法里面不会在31、32行这里new一个新的ArrayList,而是会在recursive call之后清除list最后的element。
那么区别就是在最后生成result的时候，要用new list添加。

1.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
   
2.         List<List<Integer>> res = new ArrayList();
   
3.         if(root == null) return res;
   
4.         dfs(new ArrayList(), res, root, sum);
   
5.         
   
6.         return res;
   
7.     }
   
8.    
   
9.     private void dfs(List<Integer> cur, List<List<Integer>> res, TreeNode root, int sum) {
   
10.         if(root.left == null && root.right == null) {
    
11.             if(sum == root.val) {
    
12.                 cur.add(root.val);
    
13.                 res.add(new ArrayList(cur));
    
14.                 // This is needed!!!!
    
15.                 cur.remove(cur.size() - 1);
    
16.             } else return;
    
17.         }
    
18.         
    
19.         if(root.left != null) {
    
20.             cur.add(root.val);
    
21.             dfs(cur, res, root.left, sum - root.val);
    
22.             cur.remove(cur.size() - 1);
    
23.         }
    
24.         if(root.right != null) {
    
25.             cur.add(root.val);
    
26.             dfs(cur, res, root.right, sum - root.val);
    
27.             cur.remove(cur.size() - 1);
    
28.         }
    
29.     }
    

复制代码

不知道小帅 发表于 2020-9-10 07:42
这个地方牵扯到参数传递还有call stack的内容。其实是可以用原先的，不过最后回溯的时候要恢复现场。就是之 ...

这个讲解太赞了，研究了好一会儿。。。
Permutations这道题我明白了说path自始至终只有一个，因为每次返回上一级都要remove last，所以当回到node的时候就空了。
这是说明返回的时候，参数是有可能会有变化的。参数如果是primitive types就保持不变，如果是reference就有可能会有变化？
以及，原来中文版leetcode这么强！感觉这讲解无论是官方办还是民间版都很优秀

我觉得，你可以加强以下对变量，对象等在程序中存储的理解。
一个变量：
1.什么时候存的是指针，什么时候存的是值。
2.传参的时候，传的是指针还是值


我这里正好有一道练习题，值得琢磨琢磨输出是什么，为什么输出是这样。

public static void main(String[] args) {
        int a = 1; //基础变量
        String s = "hello"; //字符串
        Point p = new Point(1,2); //变量
        Collection c = new ArrayList(); //List
        c.add(p);
        test(a,s,p,c);
        System.out.println("a:"+a);
        System.out.println("s:"+s);
        System.out.println("p:"+p);
        System.out.println("c:"+c);
}
public static void test(int a,String s,Point p,Collection c) {
        a++;
        s = s+"world";
        p.setX(a); //修改pointer对象里面x坐标值
        p = new Point(3,4);
        c.clear();
        c.add(p);
        c = new ArrayList();
        p = new Point(5,6);
        c.add(p);
}


答案：
        System.out.println("a:"+a);//答案：1
        System.out.println("s:"+s);//答案：hello
        System.out.println("p:"+p);//答案：(2,2)
        System.out.println("c:"+c);//答案：[(3,4)]

Java是pass by reference， 和指针差不多。
如果你不new 一个的， pass 进去的就是同一个list。

另外， 变量名最好不要用list这样的名字，不好。

landshark 发表于 2020-9-10 15:42
Java是pass by reference， 和指针差不多。
如果你不new 一个的， pass 进去的就是同一个list。

Java从来都是pass by value的，只不过这个value恰好是reference而已。
https://www.geeksforgeeks.org/g- ... ctly-pass-by-value/
pass by reference的意思是如果出现以下代码

1. void reset(int[] arr) {
   
2. arr = new int[1];
   
3. }
   

复制代码

这个arr会变成一个新的array，然而你可以试下，这个arr在调用的时候是什么，最后就还是什么。
再比如

1. 
   
2. void addOne(int a) {
   
3. a++;
   
4. }
   

复制代码

这个并不影响a在原函数的值，这是pass by value。
如果是C++的话。

1. 
   
2. void addOne(int &a) {
   
3. a++;
   
4. }
   

复制代码

这个操作会改变a的值，这叫Pass by reference。

这个地方牵扯到参数传递还有call stack的内容。其实是可以用原先的，不过最后回溯的时候要恢复现场。就是之前加了后来就会减掉。
可以看下这个链接里面的讲解（虽然这是另一个题目），理解一下整个过程。
https://leetcode-cn.com/problems ... a-dai-ma-by-liweiw/

不知道小帅 发表于 2020-9-10 23:37
Java从来都是pass by value的，只不过这个value恰好是reference而已。
https://www.geeksforgeeks.org/g ...

You're right, but pay attention to not only primitive types.
https://stackoverflow.com/questi ... ce-or-pass-by-value

The concept is "pass by value", but it has quite a lot under the hood.

(I was wrong. I always take Java as "pass by reference", but the terminology is wrong.)
Another good article about this:
http://www.javadude.com/articles/passbyvalue.htm

landshark 发表于 2020-9-11 00:44
You're right, but pay attention to not only primitive types.
https://stackoverflow.com/questions/ ...

对于非primitive type来说，JVM会copy一下这个object的reference，类似于存一个副本。可以改变object内部的data field，但是还是属于pass by value，就像我之前说的，只不过这个value恰好是reference而已。我了解JVM是怎么工作的，只是不希望给新人带来概念上的误导。不过这个概念确实比较容易混淆。因为object都是存在heap上面，而调用函数的参数是存在stack之上。所以每次都是重新copy一下这个reference，通过这个reference改变位于heap上的object是可行的。但是改变这个reference的指向并不会影响原先的reference，因为这只是一个副本。

cute_susu_bobo 发表于 2020-9-11 01:43
我觉得，你可以加强以下对变量，对象等在程序中存储的理解。
一个变量：
1.什么时候存的是指针，什么时候 ...

这里比较tricky的字符串，字符串是对象，所以传的也是引用，但是字符串在JVM里的处理比较特别。
可以搜搜看字符串相关的讲解