235. Lowest Common Ancestor of a Binary Search Tree

Question: Lowest Common Ancestor of a Binary Search Tree

Solution

BST 的特性：右邊的 child 大於 root; 左邊的 child 小於 root

利用上述特性：

1. 如果 p 跟 q 都大於 root，代表 p, q 都在 root 的右邊，那麼可以繼續往右邊找 LCA
2. 如果 p 跟 q 都小於 root，代表 p, q 都在 root 的左邊，那麼可以繼續往左邊找 LCA
3. 其他情況，如果給定的 p, q 跟 root 比，是一大一小的話，代表 p 跟 q 分屬於 root 的兩邊，那麼 root 就會是他們的 LCA；又或者 p, q 其中一者等於 root，那麼不論另一者在其左邊或右邊，LCA 都是 root 本人，此時就可以 return root

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

curr = root

while curr:

if p.val > curr.val and q.val > curr.val:

curr = curr.right

elif p.val < curr.val and q.val < curr.val:

curr = curr.left

else:

return curr

Video Solution