Python에서 트리 노드의 K번째 조상을 찾는 프로그램

<시간/>

0에서 n-1까지 번호가 매겨진 n개의 노드가 있는 트리가 있다고 가정합니다. 트리는 부모 배열에 의해 제공되며, 여기서 parent[i]는 노드 i의 부모입니다. 트리의 루트는 노드 0입니다. 주어진 노드의 k번째 조상을 찾아야 합니다. 조상이 없으면 -1을 반환합니다.

따라서 입력이 다음과 같으면

노드 6의 첫 번째 조상은 5이고 두 번째는 2이기 때문에 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

solve() 함수를 정의합니다. 이것은 부모, 노드, k
를 취합니다.
노드가 -1과 같으면
- 반환 -1
그렇지 않으면 k가 1과 같을 때
- 부모[노드]
  반환
그렇지 않으면 (k AND k-1)이 0이면
- solve(parent, solve(parent, node, 몫 k/2) , 몫 k/2)
  반환
그렇지 않으면
- msb :=2^(k의 비트 수 -1)
- 해결(부모, 해결(부모, 노드, k-msb), msb)
  반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(parent, node, k):
   if node == -1:
      return -1
   elif k == 1:
      return parent[node]
   elif not (k & k-1):
      return solve(parent, solve(parent, node, k >> 1), k >> 1)
   else:
      msb = 1 << (k.bit_length()-1)
      return solve(parent, solve(parent, node, k-msb), msb)

parent = [-1,0,0,1,2,2,5,5]
node = 6
k = 2
print(solve(parent, node, k))

입력

[6,7,9,16,22], 2