二叉樹遍歷的時間效率

Question

這是一個leetcode問題。 「給定一棵二叉樹和一個和，找到每個路徑的總和等於給定總和的所有根到葉路徑。」但是由於時間超出限制，我的代碼無法通過測試用例。但解決方案代碼（https://oj.leetcode.com/discuss/15169/14-line-solution-in-java-using-recursion）可以通過測試用例。我不知道有兩個版本代碼有什麼大的區別嗎？

我的代碼：

public class Solution { 
    List<List<Integer>> res = new ArrayList<List<Integer>>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) { 
    if (root == null) 
     return res; 
    List<Integer> t = new ArrayList<Integer>(); 
    has(root, sum, t); 
    return res; 
    } 

    public void has(TreeNode root, int sum, List<Integer> t) { 
    if (root == null) 
     return; 
    if (root.left == null && root.right == null && sum == root.val) { 
     t.add(root.val); 
     res.add(t); 
     return; 
    } 
    t.add(root.val); 
    has(root.right, sum - root.val, t); 
    has(root.left, sum - root.val, t); 
    return; 
    } 
} 

解決方案：

public class Solution { 

    public static List<List<Integer>> pathSum(TreeNode root, int sum) { 
     List<List<Integer>> list = new ArrayList<List<Integer>>(); 
     if(root==null) return list; 
     if (root.val==sum && root.left==null && root.right==null) { 
     list.add(new ArrayList<Integer>()); 
     list.get(list.size()-1).add(root.val); 
     return list; 
     } 
     list.addAll(pathSum(root.left, sum-root.val)); 
     list.addAll(pathSum(root.right, sum-root.val)); 
     for(List<Integer> l:list) 
      l.add(0, root.val); 
     return list; 
    } 
    } 

Answer 1

列表是一個對象。如果您將List傳遞給您的方法，它將在該方法中被視爲局部變量。在你的方法結束時，該局部變量將被垃圾收集（刪除）。

您將一個節點添加到您的列表，然後遞歸地調用該方法傳遞該列表。當你最終擊中微不足道的情況時（你擊中了一片葉子）。您的方法將結束並返回以繼續運行調用它的（相同）方法。你沒有返回任何東西，List的實例將被垃圾收集（刪除）。所以這意味着你的列表中缺少葉子（因爲具有它的本地列表被刪除）。它將繼續這樣做，並且你的pathSum方法最終會返回一個空List。我無法分辨爲什麼它超過了時間限制，但是你的代碼不正確。

請注意，在解決方案中，該方法返回添加新節點的列表。所以調用它的方法已經存儲了。在你的實現中，你什麼也沒有返回，調用它的方法沒有將List和新的Node一起存儲，因此被垃圾回收。

我希望這可以澄清你的問題。如果不能隨意讓我知道。