java - Time efficiency of binary tree traversal -

java - Time efficiency of binary tree traversal -

this leetcode question. "given binary tree , sum, find root-to-leaf paths each path's sum equals given sum." code can't pass test case because of time exceeded limit. solution code(https://oj.leetcode.com/discuss/15169/14-line-solution-in-java-using-recursion) can pass test case. don't figure out there big difference 2 version codes?

my code:

public class solution { list<list<integer>> res = new arraylist<list<integer>>(); public list<list<integer>> pathsum(treenode root, int sum) { if (root == null) homecoming res; list<integer> t = new arraylist<integer>(); has(root, sum, t); homecoming 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; } }

solution:

public class solution { public static list<list<integer>> pathsum(treenode root, int sum) { list<list<integer>> list = new arraylist<list<integer>>(); if(root==null) homecoming list; if (root.val==sum && root.left==null && root.right==null) { list.add(new arraylist<integer>()); list.get(list.size()-1).add(root.val); homecoming 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); homecoming list; } }

list object. if pass list method, treated local variable within method. @ end of method, local variable garbage collected (deleted).

you add together node list , phone call method recursively passing list. when nail trivial case (you nail leaf ). method end , homecoming go on running (same) method called it. you're not returning , instance of list garbage collected (deleted). means leaf missing list (because local list had deleted). go on doing , and pathsum method homecoming empty list. can't tell why exceeds time limit code not correct.

note in solution method returns list in new node added. method called has stored. in implementation, homecoming nil , method called didn't store list new node, , hence garbage collected.

i hope clarifies problem. if not sense free allow me know.

java performance time