首页 > 代码库 > Leetcode: Path Sum II

Leetcode: Path Sum II

2024-07-05 17:49:40   223人阅读

这是一道很常见的题，看题的时候看漏了root to leaf的leaf，以为只要从root开始就可以了，太不仔细了，sigh~ 其实类似的题目在Career Cup的4.9，那个题是任意路径，不必从root到leaf，要求更高。

一直以来我都有这样的疑问，迭代的变量（如下例中的path、total）如果在迭代中发生改变，返回上一层进行新的迭代的时候，调用这个变量，是用新的改变后的那个变量呢，还是用原来的？比如：

 1     public void getpath(ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> path, int total, TreeNode root, int sum) {
 2         if (root == null) return;
 3         path.add(root.val);
 4         total = total + root.val;
 5         if (total == sum && root.left == null && root.right == null) {
 6             paths.add(new ArrayList<Integer>(path));
 7         }
 8         getpath(paths, path, total, root.left, sum);
 9         getpath(paths, path, total, root.right, sum);
10         path.remove(path.size() - 1);
11         total = total - root.val;
12     }

比如这段代码中root.left和root.right的两段recursion，这个recursion中会对path和total进行改变。我在想，如果这两段迭代完了之后，返回上一层，上一层进行新的迭代，是不是使用update了之后的path和total呢？

对java而言答案是的。任何分支对path变量的改变将要被保留。path变量始终只有唯一的一个，而不存在拷贝什么的，如果在root.left的recursion中改变了path，进入root.right的recursion，path变量就已经是新的path变量了！

这一点和C恰恰相反，众所周知C语言函数用形参去拷贝实参，用形参进行一系列运算之后即使发生改变，不会对实参造成任何影响，实参还是原来的那个。所以如果上述例子是在C语言中，path就还是原来那一个！如果你想要path变化，就得用path的地址

正因为java中，任何分支对变量的改变会保存下来，所以我们才在末尾要加上path.remove(path.size() - 1)； 以便能够尝试新的可能性。

代码：

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
12         ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
13         ArrayList<Integer> path = new ArrayList<Integer>();
14         int total = 0;
15         getpath(paths, path, total, root, sum);
16         return paths;
17     }
18     
19     public void getpath(ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> path, int total, TreeNode root, int sum) {
20         if (root == null) return;
21         path.add(root.val);
22         total = total + root.val;
23         if (total == sum && root.left == null && root.right == null) {
24             paths.add(new ArrayList<Integer>(path));
25         }
26         getpath(paths, path, total, root.left, sum);
27         getpath(paths, path, total, root.right, sum);
28         path.remove(path.size() - 1);
29         total = total - root.val;
30     }
31 }

 

 


联系
我们