9 
path = 0 # the lenght of the path
    while self.right != None or self.left != None:
        while self.right != None:
            self = self.right
            path = path +1 
        while self.left != None:
            self = self.left
            path = path +1
    return path

これは、高さを見つけるための私のサンプルコードであり、自己から葉までのノード数による最長パスの長さとして定義されます。リーフノードの高さは1です。

動作しません。

4

6 に答える 6

25

あなたがしていることは再帰的ではなく、反復的です。再帰は次のようになります。

def height(node):
    if node is None:
        return 0
    else:
        return max(height(node.left), height(node.right)) + 1
于 2012-11-10T14:05:26.697 に答える
6

あなたはマタから解決策を与えられましたが、コードを見て、それが何をしているのかを理解することをお勧めします:

    while self.right != None:
        self = self.right
        path = path +1

これは何をしますか？適切な子、次にその適切な子、というように検索されます。したがって、これは「一番右」の葉の 1 つのパスのみをチェックします。

これは左側についても同じことを行います:

   while self.left != None:
        self = self.left
        path = path +1

再帰の考え方は、各部分問題について、他のすべての部分問題とまったく同じレシピを使用して解決することです。したがって、サブツリーまたはリーフのみにアルゴリズムを適用する場合でも、アルゴリズムは機能します。

また、再帰的な定義はそれ自体を呼び出します (ループを使用してこれを実装することはできますが、ここでは範囲を超えています)。

定義を思い出してください:

再帰: 再帰の定義を参照してください。

;)

于 2012-11-10T14:35:47.483 に答える