Time Limit Exceeded? (Java Solution)

  • 0

    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; 
                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; 
                current = s.pop(); 
                if(current==target) return true; 
            return false; 

  • 2

    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.