註意！JAVA中的值傳遞

前言：今天在解決一個問題時，程式總是不能輸出正確值，分析邏輯思路沒問題後，發現原來是由於函數傳遞導致了這個情況。

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大基本數據類型，且均有對應的包裝類

在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 ---

結論：調用構造函數後，函數指向新的對象，原對象的值發生改變，函數內值也不會改變。同理，新對象的值發生改變，原對象的值也不會發生改變。