Time Limit Exceeded? (Java Solution)


  • 0
    K

    Not sure why my Java solution is exceeding the time limit. Any advice?

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return helper(root, p, q); 
        }
        
        public TreeNode helper(TreeNode root, TreeNode p, TreeNode q){
            if(root==p || root==q) return root; 
            else{
                if(dfsSearch(root.left, p) && dfsSearch(root.left, q)){
                    //both p and q are to the left, go left
                    return helper(root.left, p, q); 
                } else if (dfsSearch(root.right, p) && dfsSearch(root.right, q)){
                    return helper(root.right, p, q);
                }
                return root; 
            }
        }
        
        public boolean dfsSearch(TreeNode root, TreeNode target){
            Stack<TreeNode> s = new Stack<TreeNode>(); 
            if(root!=null) s.push(root); 
            TreeNode current; 
            while(!s.isEmpty()){
                current = s.pop(); 
                if(current==target) return true; 
                if(current.right!=null){
                    s.push(current.right);
                }
                if(current.left!=null){
                    s.push(current.left);
                }
            }
            return false; 
        }
    }

  • 2
    S

    You're repeating the DFS at each layer in the tree. So if p and q are n layers down, you would'e called DFS at each of the n layers to get to them, resulting in O(n^2) runtime.

    Conceptually you only need to locate p and q once. For example you could do a DFS for p, then a DFS for q, but save the paths to each and then find where the paths diverge.

    You can also do it without saving the paths with a single DFS.


Log in to reply
 

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