LCDistanceK

class Solution:
  def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
    if not k:
      return [target.val]
    
    parent = {}

    def parents(n, p):
      if n:
        if p:
          parent[n.val] = p
        parents(n.left, n)
        parents(n.right, n)
  
    parents(root, None)

    res = []

    def findNodes(n, level):
      if n:
        if level == 0:
          res.append(n.val)
        else:
          findNodes(n.left, level-1)
          findNodes(n.right, level-1)


    # Children of Target
    findNodes(target, k)

    i = k-1
    n = parent.get(target.val, None)
    prev = target

   # Ancestors or Siblings
    while i > 0 and n:
      findNodes(n.left if n.left != prev else n.right, i-1)
      i = i-1
      prev = n
      n = parent.get(n.val, None)
    
    if n:
      res.append(n.val)
  
    return res