Leetcode # 235. Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree

First Solution

Time Complexity: O(len(tree))
Space Complexity: O((len(tree)) ^ 2)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    stack = [[root, []]] if root else []
    ancestors_p, ancestors_q = None, None
    while stack and (not ancestors_p or not ancestors_q):
      cur, ancestors = stack.pop()
      next_ancestors = ancestors + [cur]
      if cur is p:
        ancestors_p = next_ancestors
      if cur is q:
        ancestors_q = next_ancestors
      for child in [cur.left, cur.right]:
        if child:
          stack.append([child, next_ancestors])
    min_ancestors_len = min(len(ancestors_p), len(ancestors_q))
    for i in range(min_ancestors_len):
      if i == min_ancestors_len - 1 or ancestors_p[i + 1] is not ancestors_q[i + 1]:
        return ancestors_p[i]

Better Solution

利用 Binary Search Tree 的特性，
當p , q 不再同於此 node 的 left/right subtree 中時
該 node 為 Lowest Common Ancestor

Time Complexity: O(len(tree))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    cur = root
    pq_min, pq_max = min(p.val, q.val), max(p.val, q.val)
    while cur and (pq_min > cur.val or pq_max < cur.val):
      cur = cur.right if pq_min > cur.val else cur.left
    return cur

Last Updated on 2023/09/12 by A1go