前言：今天在解决一个问题时，程序总是不能输出正确值，分析逻辑思路没问题后，发现原来是由于函数传递导致了这个情况。

LeetCode 113

问题：给你二叉树的根节点root和一个整数目标和targetSum，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

示例

 

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

我的代码如下

 1 class Solution {
 2     public void traversal(TreeNode root, int count, List<List<Integer>> res, List<Integer> path) {
 3         path.add(root.val);
 4         if (root.left == null && root.right == null) {
 5             if (count - root.val == 0) {
 6                 res.add(path);
 7             }
 8             return;
 9         }
10 ​
11         if (root.left != null) {
12             traversal(root.left, count - root.val, res, path);
13             path.remove(path.size() - 1);
14         }
15         if (root.right != null) {
16             traversal(root.right, count - root.val, res, path);
17             path.remove(path.size() - 1);
18         }
19     }
20 ​
21     public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
22         List<List<Integer>> res = new ArrayList<>();
23         List<Integer> path = new ArrayList<>();
24         if (root == null) return res;
25         traversal(root, targetSum, res, path);
26 ​
27         return res;
28     }
29 }

该题的思路是采用递归，traversal函数内root是当前树的根节点，count是目标值，res是存储结果，path是路径。该代码对于示例的输入输出为

1 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
2 输出：[[5],[5]]

经过排查最终问题在于代码中的add方法

原代码部分内容为

1 if (root.left == null && root.right == null) {
2     if (count - root.val == 0) {
3         res.add(path);
4     }
5     return;
6 }

该部分内容需要改为

1 if (root.left == null && root.right == null) {
2     if (count - root.val == 0) {
3         res.add(new ArrayList(path));
4     }
5     return;
6 }

此时所有代码对于示例的输入输出为

1 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
2 输出：[[5,4,11,2],[5,8,4,5]]

在java中，存在8大基本数据类型，且均有对应的包装类

数据类型 占用位数 默认值 包装类
byte(字节型) 8 0 Byte
short(短整型) 16 0 Short
int(整型) 32 0 Integer
long(长整型) 64 0.0l Long
float(浮点型) 32 0.0f Float
double(双精度浮点型) 64 0.0d Double
char(字符型) 16 '/u0000' Character
boolean(布尔型) 1 false Boolean

在java中，函数传递只有值传递，是指在调用函数时，将实际参数复制一份传递给函数，这样在函数中修改参数(形参)时，不会影响到实际参数。

基本数据类型的值传递

测试类

 1 public class TestClass {
 2     public static void test(int value) {
 3         value = 2;
 4         System.out.println("形参value的值：" + value);
 5     }
 6 ​
 7     public static void main(String[] args) {
 8         int value = 1;
 9         System.out.println("调用函数前value的值：" + value);
10         test(value);
11         System.out.println("调用函数后value的值：" + value);
12     }
13 }

结果为

1 调用函数前value的值：1
2 形参value的值：2
3 调用函数后value的值：1

结论：可以看到，int类型的value初始为1，调用函数后，value仍然为1，基本数据类型在函数中修改参数(形参)时不会影响到实参的值。

引用数据类型的值传递

类TreeNode

 1 public class TreeNode {
 2     int val;
 3     TreeNode left;
 4     TreeNode right;
 5 ​
 6     TreeNode() {
 7     }
 8 ​
 9     TreeNode(int val) {
10         this.val = val;
11     }
12 ​
13     TreeNode(int val, TreeNode left, TreeNode right) {
14         this.val = val;
15         this.left = left;
16         this.right = right;
17     }
18 }

测试类1

 1 public class TestClass {
 2     public static void test(TreeNode node) {
 3         node.val = 2;
 4         System.out.println("形参node的val值：" + node.val);
 5     }
 6 ​
 7     public static void main(String[] args) {
 8         TreeNode node = new TreeNode(1);
 9         System.out.println("调用函数前node的val值：" + node.val);
10         test(node);
11         System.out.println("调用函数后node的val值：" + node.val);
12     }
13 }

结果为

1 调用函数前node的val值：1
2 形参node的val值：2
3 调用函数后node的val值：2

结论：可以看到，TreeNode类型的node对象的val值初始为1，调用函数后，node对象的val值被修改为2，引用数据类型在函数中修改参数(形参)时影响到了实参的值。

现在看另一个示例

测试类2

 1 public class TestClass {
 2     public static void test(TreeNode node) {
 3         node = new TreeNode(2);
 4         System.out.println("形参node的val值：" + node.val);
 5     }
 6 ​
 7     public static void main(String[] args) {
 8         TreeNode node = new TreeNode(1);
 9         System.out.println("调用函数前node的val值：" + node.val);
10         test(node);
11         System.out.println("调用函数后node的val值：" + node.val);
12     }
13 }

结果为

1 调用函数前node的val值：1
2 形参node的val值：2
3 调用函数后node的val值：1

结论：可以看到，TreeNode类型的node对象的val值初始为1，调用函数后，node对象的val值仍然为1，引用数据类型在函数中修改参数(形参)时未影响到实参的值。

那么，为什么会出现这种问题呢？

首先，在JAVA中，函数传递都是采用值传递，实际参数都会被复制一份给到函数的形式参数，所以形式参数的变化不会影响到实际参数，基本数据类型的值传递示例可以发现这个性质。但引用数据类型的值传递为什么会出现修改形式参数的值有时会影响到实际参数，而有时又不会影响到实际参数呢？其实引用数据类型传递的内容也会被复制一份给到函数的形式参数，这个内容类似C++中的地址，示例中的node对象存储于堆中，虽然形参与实参是两份内容，但内容值相同，都指向堆中相同的对象，故测试类1在函数内修改对象值时，函数外查看时会发现对象值已被修改。测试类2在函数内重新构造了一个对象node，在堆中申请了一个新对象(新对象与原对象val值不相同)，让形参指向这个对象，所以不会影响到原对象node的值。测试类1与测试类2的区别在于引用数据类型的指向对象发生了变化。

以下代码可验证上述分析

测试类1

 1 public class TestClass {
 2     public static void test(TreeNode node) {
 3         System.out.println("test:node" + node);
 4         node.val = 2;
 5         System.out.println("test:node" + node);
 6         System.out.println("形参node的val值：" + node.val);
 7     }
 8 ​
 9     public static void main(String[] args) {
10         TreeNode node = new TreeNode(1);
11         System.out.println("调用函数前node的val值：" + node.val);
12         System.out.println("main node:" + node);
13         test(node);
14         System.out.println("调用函数后node的val值：" + node.val);
15         System.out.println("main node:" + node);
16     }
17 }

结果为

1 调用函数前node的val值：1
2 main node:TreeNode@1540e19d
3 test:nodeTreeNode@1540e19d
4 test:nodeTreeNode@1540e19d
5 形参node的val值：2
6 调用函数后node的val值：2
7 main node:TreeNode@1540e19d

测试类2

 1 public class TestClass {
 2     public static void test(TreeNode node) {
 3         System.out.println("test:node" + node);
 4         node = new TreeNode(2);
 5         System.out.println("test:node" + node);
 6         System.out.println("形参node的val值：" + node.val);
 7     }
 8 ​
 9     public static void main(String[] args) {
10         TreeNode node = new TreeNode(1);
11         System.out.println("调用函数前node的val值：" + node.val);
12         System.out.println("main node:" + node);
13         test(node);
14         System.out.println("调用函数后node的val值：" + node.val);
15         System.out.println("main node:" + node);
16     }
17 }

结果为

1 调用函数前node的val值：1
2 main node:TreeNode@1540e19d
3 test:nodeTreeNode@1540e19d
4 test:nodeTreeNode@677327b6
5 形参node的val值：2
6 调用函数后node的val值：1
7 main node:TreeNode@1540e19d

对于测试类1，形参和实参都是指向相同的对象，所以利用形参修改对象的值，实参指向的对象的值发生改变。对于测试类2，形参在函数开始和实参指向相同的对象，让其指向新的对象后，实参指向的对象的值不会发生改变。简要说，测试类1形参复制了实参的地址，修改了地址对应的对象值，但并未修改地址值，测试类2形参复制了实参的地址，并修改了地址值，但并未修改原地址值对应的对象值。

有了目前的结论，可以理解为什么res.add()函数内path修改为new ArrayList(path)就可代码运行成功。因为我的path类型为List<Integer>，为引用数据类型，且path的值一直在发生变化。随着递归代码的运行，path的值发生变化，res内最初的List<Integer>值会发生变化(就是path的值)。但将path修改为new ArrayList(path)后，是在堆中新构造了对象，并指向该对象，原对象的变化不会影响到该对象的值，那么res内List<Integer>值就不会发生变化。

listList.add()方法直接传入list1

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 ​
 4 public class TestClass {
 5     public static void main(String[] args) {
 6         List<List<Integer>> listList = new ArrayList<>();
 7         List<Integer> list1 = new ArrayList<>();
 8         list1.add(1);
 9         listList.add(list1);  //直接add list1
10         List<Integer> list2 = new ArrayList<>();
11         list2.add(2);
12         listList.add(list2);
13         System.out.println("list1改变前");
14         for (List<Integer> l : listList) {
15             for (Integer i : l) {
16                 System.out.println(i);
17             }
18             System.out.println("---");
19         }
20         list1.set(0, 2);    //将list1的0号元素改为2
21         System.out.println("list1改变后");
22         for (List<Integer> l : listList) {
23             for (Integer i : l) {
24                 System.out.println(i);
25             }
26             System.out.println("---");
27         }
28     }
29 }

结果为

 1 list1改变前
 2 1
 3 ---
 4 2
 5 ---
 6 list1改变后
 7 2
 8 ---
 9 2
10 ---

listList.add()方法重新构造新对象（内容与list1相同）

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 ​
 4 public class TestClass {
 5     public static void main(String[] args) {
 6         List<List<Integer>> listList = new ArrayList<>();
 7         List<Integer> list1 = new ArrayList<>();
 8         list1.add(1);
 9         listList.add(new ArrayList<>(list1)); //构造新对象 再调用add
10         List<Integer> list2 = new ArrayList<>();
11         list2.add(2);
12         listList.add(list2);
13         System.out.println("list1改变前");
14         for (List<Integer> l : listList) {
15             for (Integer i : l) {
16                 System.out.println(i);
17             }
18             System.out.println("---");
19         }
20         list1.set(0, 2);    //将list1的0号元素改为2
21         System.out.println("list1改变后");
22         for (List<Integer> l : listList) {
23             for (Integer i : l) {
24                 System.out.println(i);
25             }
26             System.out.println("---");
27         }
28     }
29 }

结果为

 1 list1改变前
 2 1
 3 ---
 4 2
 5 ---
 6 list1改变后
 7 1
 8 ---
 9 2
10 ---

 

结论：调用构造函数后，函数指向新的对象，原对象的值发生改变，函数内值也不会改变。同理，新对象的值发生改变，原对象的值也不会发生改变。