Why does this code give time limit exceeded? Java


  • 8
    P
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public LinkedList<LinkedList<Integer>> pathSum(TreeNode root, int sum) {
            LinkedList<Integer> list = new LinkedList<Integer>();
            LinkedList<LinkedList<Integer>> bigList = new LinkedList<LinkedList<Integer>>();
            get(root,sum,0,list,bigList);
            return bigList;
        }
        public void get(TreeNode node, int target, int sum, LinkedList<Integer> list, LinkedList<LinkedList<Integer>> bigList){
            if (node == null) return;
            int number = sum + node.val;
            if (number == target && node.left == null && node.right == null){// leaf & target check
                list.add(node.val);//add it to list
                bigList.add(list);//add list to big list
                return;
            }
            else {
                list.add(node.val);
                //recurse
                if (node.left != null) get(node.left, target, number, list, bigList);
                if (node.right != null) get(node.right, target, number, list, bigList);
            }
        }
        
    }
    

    For the test case:
    [1,1,#,1,#...,1,#,1] 1000"


  • 0
    B

    my code has the same approach and also has same issue.


  • 10
    Y

    You know in Java, if you use the object as parameter, then in the recursive function the parameter will always refer to the same object, which means the list you used is keep adding without removing element... And I guess the answer shall be wrong too.. Here is my code, though it looks ugly..

    public class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null)
            return result;
        calculate(root,sum,new ArrayList<Integer>());
        return result;
    }
    public void calculate(TreeNode root,int sum,List<Integer> path){
         path.add(root.val);
        if(root.left==null&&root.right==null){
            if(sum-root.val==0){
                result.add(new ArrayList<Integer>(path));
            }
        }
        else{
            if(root.left!=null)
                calculate(root.left,sum-root.val,path);
            if(root.right!=null)
                calculate(root.right,sum-root.val,path);
        }
        path.remove(path.size()-1);
        return;
    }
    

    }

    cheers~


  • 0
    P

    Thanks a lot. I should have copied contents to a newly initialized list before the next recursive calls.


  • 0
    A

    In the last line, what you missed is deleting "node.val" from list, which you added previously.
    You need to "undo" the change you made to list, at the end of each recursion.
    I think you may not just end up with TLE, but also wrong answer.


  • -1
    W

    your answer is wrong , you should define a new List when a recursive start


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.