PythonでツリーノードのK番目の祖先を見つけるプログラム

0からn-1までの番号が付けられたn個のノードを持つツリーがあるとします。ツリーは親配列によって与えられます。ここで、parent[i]はノードiの親です。ツリーのルートはノード0です。特定のノードのk番目の祖先を見つける必要があります。祖先が存在しない場合は、-1を返します

したがって、入力が次のような場合

ノード6の最初の祖先が5で、2番目の祖先が2であるため、出力は2になります。

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これは親、ノード、kを取ります

• ノードが-1と同じ場合、

  • -1を返す

• それ以外の場合、kが1と同じ場合、

  • 親を返す[ノード]

• それ以外の場合、（k AND k-1）がゼロの場合、

  • 戻り値solve（parent、solve（parent、node、quotient of k / 2）、quotient of k / 2）

• それ以外の場合

  • msb：=2 ^（k -1のビット数）

  • 戻り値solve（parent、solve（parent、node、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

出力

2