Python Iterative Solution


  • 16
    T
    class Solution:
    
    def lowestCommonAncestor(self, root, p, q):
        while root:
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                return root

  • 7
    B

    A bit simpler:

    def lowestCommonAncestor(self, root, p, q):
        while root:
            if max(p.val, q.val) < root.val:
                root = root.left
            elif min(p.val, q.val) > root.val:
                root = root.right
            else:
                return root
        return None

  • 1
    C

    A small (math) trick to make it shorter :

    if the value of x is between a and b, then (x-a)*(x-b)<=0

    def lowestCommonAncestor(self, root, p, q):
        while (root.val-p.val)*(root.val-q.val) > 0:
            if root.val > max(p.val, q.val):
                root = root.left
            else:
                root = root.right
        return root
    

    same idea but even shorter (Python!):

    def lowestCommonAncestor(self, root, p, q):
        while (root.val-p.val)*(root.val-q.val) > 0:
            root = (root.right, root.left)[root.val>max(p.val, q.val)]
        return root
    

Log in to reply
 

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