Leetcode # 1483. ⭐️ Kth Ancestor of a Tree Node

Problem

https://leetcode.com/problems/kth-ancestor-of-a-tree-node

First Solution: Binary Lifting
[Time Limit Exceeded  8 / 17 testcases passed]

Time Complexity: O(n ** 2)
__init__(): worst case – O((n – 2) * (n – 2) / 2) = O(n ** 2) (當所有節點都只有一個 child 時)
getKthAncestor(): O(log(k))
Space Complexity: O(n * log(n))
(The input and output generally do not count towards the space complexity.)

class TreeAncestor:

  def __init__(self, n: int, parent: List[int]):
    self.ancestors = [[] for _ in range(n)]
    for i in range(1, n):
      curr = i
      depth = ceil(log2(n + 1))
      for j in range(depth):
        for t in range(2 ** (j - 1) if j > 0 else 1):
          curr = None if curr == 0 or curr is None else parent[curr]
          if curr is None: break
        if curr is not None:
          self.ancestors[i].append(curr)

  def getKthAncestor(self, node: int, k: int) -> int:
    curr = node
    while k:
      exponent = floor(log2(k))
      if exponent >= len(self.ancestors[curr]):
        return -1
      curr = self.ancestors[curr][exponent]
      k -= 2 ** exponent
    return curr

Revised Solution: Binary Lifting

Time Complexity: O(n)
__init__(): O(n)
getKthAncestor(): O(log(k))
Space Complexity: O(n * log(n))
(The input and output generally do not count towards the space complexity.)

class TreeAncestor:

  def __init__(self, n: int, parent: List[int]):
    self.limit = n
    parent = dict(enumerate(parent)) # {i: parent[i] for i in range(len(parent))}
    self.ancestors = [parent]
    for step in range(self.limit):
      ancestor = {}
      prev_a = self.ancestors[-1]
      for i in prev_a:
        if prev_a[i] in prev_a:
          ancestor[i] = prev_a[prev_a[i]]
      if not ancestor:
        self.limit = step
        break
      self.ancestors.append(ancestor)

  def getKthAncestor(self, node: int, k: int) -> int:
    curr, _k = node, k
    while _k > 0 and curr > -1:
      exponent = min(floor(log2(_k)), self.limit)
      curr = self.ancestors[exponent].get(curr, -1)
      _k -= 2 ** exponent
    
    return curr

Last Updated on 2023/09/19 by A1go