recursion - 二分木の中央値ノード

Question

答えられなかった次の質問で試験を受けました。各ノードが特定の高さ（下から）と特定の深さ（ルートから）を持つ二分木があります。両方をゼロから数え始めます。例：ルートに子が1つあるツリーの場合、子の深さは1、高さは0になります。

すべての中央値ノードを出力する再帰アルゴリズムを見つけます。つまり、ノードの高さがその深さに等しい場合です。

次のようなヒントが与えられました。関数の引数としてd（depth）を指定し、戻り値としてheightを指定します。

Answer 1

node が attribute を持つオブジェクトである Python 実装children。

def R(node, d):
  if not node.children: # No children, leaf node
    height = 0
  else:
    height = max( R(child, d+1) for child in node.children ) + 1
  if height == d:
    print node  # Or some node.id
  return height

R(root, 0)  # Call with a root node