Time Limit Exceed - Please help


  • 0
    K

    I am trying to use DFS to solve this problem but I got "Time Limit Exceed" error for the test case {1 # 1 # 1 # ... } 1000
    Any suggestions to improve my code? Thanks

    public List<List<Integer>> pathSum(TreeNode root, int sum) 
    {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        
        if (root == null)
        {
            return result;
        }
        
        LinkedList<Integer> list = new LinkedList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        LinkedList<TreeNode> visited = new LinkedList<TreeNode>();
        stack.push(root);
        int tempSum = 0;
        
        while (!stack.isEmpty())
        {
            TreeNode temp = stack.peek();
            
            if (!visited.contains(temp))
            {
                list.add(temp.val);
                visited.add(temp);
                tempSum += temp.val;
            }
            
            if (temp.left == null && temp.right == null && tempSum == sum)
            {
                LinkedList<Integer> tempList = new LinkedList<Integer>(list);
                result.add(tempList);
            }
            
            if (temp.left != null && !visited.contains(temp.left))
            {
                stack.push(temp.left);
            }
            else if (temp.right != null && !visited.contains(temp.right))
            {
                stack.push(temp.right);
            }
            else
            {
                tempSum -= stack.pop().val;
                list.removeLast();
            }
        }
        
        return result;
    }

Log in to reply
 

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