Эффективность времени обхода двоичного дерева

Question

Это вопрос в литкоде. «Учитывая двоичное дерево и сумму, найдите все пути от корня до листа, где сумма каждого пути равна данной сумме». Но мой код не может пройти тест из-за превышения времени. Но код решения (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 в конечном итоге вернет пустой список. Я не могу понять, почему он превышает срок, но ваш код неверен.

Обратите внимание, что в решении метод возвращает список, в который добавлен новый узел. Таким образом, метод, который его вызвал, хранит его. В вашей реализации вы ничего не возвращаете, и метод, который его вызвал, не сохранил Список с новым узлом, и поэтому собран мусор.

Надеюсь, это прояснит вашу проблему. Если не стесняйтесь, дайте мне знать.