Leetcode # 1644. Lowest Common Ancestor of a Binary Tree II

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

Solution: DFS

Time Complexity: O(2 * len(tree)) = O(2 * len(tree))
Space Complexity: O(len(tree)) (The worst case is O(2 * len(tree)))
(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, []]]
    p_ancestors = q_ancestors = None
    while stack:
      cur, ancestors = stack.pop()
      ancestors = ancestors.copy() + [cur]
      for child in [cur.left, cur.right]:
        if child:
          if child == p:
            p_ancestors = ancestors.copy() + [child]
          if child == q:
            q_ancestors = ancestors.copy() + [child]
          stack.append([child, ancestors])

    if not p_ancestors or not q_ancestors:
      return None
    # print([node.val for node in p_ancestors])
    # print([node.val for node in q_ancestors])
    for i in range(min(len(p_ancestors), len(q_ancestors))):
      if p_ancestors[i] != q_ancestors[i]:
        return p_ancestors[i - 1]
    return p_ancestors[-1] if len(p_ancestors) < len(q_ancestors) else q_ancestors[-1]

Solution: DFS (Recursive)

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

class Solution:
  def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    self.lca = None

    def dfs(_root, _p, _q):
      if self.lca:
        return 0

      found = 0
      if _root == _p and _root == _q:
        self.lca = _root
        return 0
      if _root == _p:
        found += 1
      if _root == _q:
        found += 1

      for child in [_root.left, _root.right]:
        if child:
          found += dfs(child, _p, _q)

      if found == 2:
        self.lca = _root
        return 0
    
      return found

    dfs(root, p, q)
    return self.lca
      

Last Updated on 2023/08/16 by A1go