AC non-recursive java code of lgn average time complexity, corner cases taken into account.


  • 0
    R

    A simple and clean code can be referred to the following, which is lgn average time complexity:
    java code

    However, the aforementioned code does not consider corner cases, such as:

    1. at least one of root, p, and q is null;

    2. at least one of p & q is not a node in the tree rooted at root.

    The following code with lgn average time complexity can deal with above corner cases.

        private boolean binarySearch(TreeNode t, TreeNode n){
        if(t==null) return false;
        if(t.val == n.val) return true;
        return n.val<t.val? 
                binarySearch(t.left, n) : 
                binarySearch(t.right, n);
        }
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          if(root==null || p==null || q==null || 
              !binarySearch(root, p) || !binarySearch(root, q)) 
                  return null;
          if(p.val == q.val) return p;
          TreeNode r = root;
          while((p.val-r.val)*(q.val-r.val) > 0)
              r = p.val<r.val? r.left : r.right;
          return r;
        }
    

  • 0
    J

    I don't think it is a non-recursive solution...your binarySearch function is recursive.


  • 0
    J

    Here is my non-recursive solution:

    public class Solution {
           public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
                 TreeNode lowest = null;     
                 
           while (root != null) {
                 if (p.val == root.val || q.val == root.val || (p.val < root.val && q.val > root.val) || (p.val > root.val && q.val < root.val)) {
                     lowest = root;
                     break;
                 } else if (p.val < root.val && q.val < root.val) {
                     root = root.left;
                 } else root = root.right;
            }   
    
            return lowest;
        }
    }

  • 0
    R

    You are right, and thanks for let me know it.


  • 0
    R

    The code will fail for the corner case: p or q is not in the tree. Nevertheless, this is a neat solution.


  • 0
    J

    It p or q doesn't exit, eventually the while loop will end because root turns null, and lowest will return null because I defined it out of the while loop.


  • 0
    R

    fail case: [2, 1, 3], 0, 4. root.val=2, lowest = root will be returned. In fact, however, p & q do NOT have a LCA.


  • 0
    J

    Yes, you are right, anyway, my solution is AC now, looks like they don't have such test case. But you are right, probably I should check if p or/and q doesn't exist.


Log in to reply
 

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