再帰とバイナリツリー

Question

#Get length of the longest path through recursion 
def max_height(node): 
    if not node: 
     return 0 
    left = max_height(node.left) #Base Case based on my understanding 
    right = max_height(node.right) #Base Case based on my understanding 
    return max_height(left, right) + 1 

長さを取得するためにmax_heightを呼び出し続けますが、エラーが発生します。私は3つの可能性を考えました：

1）私はベースケースの概念を誤解しています。私は実際にベースケースを持っていません。

2）私はPythonコードを正しく配置していません。

3）私は再帰的にBSTの高さを取得するのではなく、ツリーの幅を取得します。これは後の計算に影響します。

私はそれがこの質問に似ていることを知っていますが、主な違いは、私は実際には反復を使用しようとしていることです。 how to find the height of a node in binary tree recursively

Answer 1

1. ベースケースはここで再帰が停止してい1：私はあなただけのタブを使用していることを確認してください...間隔で問題が表示されていないnot node（node == None）

2. またはスペースのみ

3. これは、最長のルートリーフパスに沿ったルートからリーフまでのノードの数を生成します。すべてのノードレベルで、1を追加し、上位のサブツリーに従います。

   def max_height(node): 
       if not node: # this is the base case: 
        return 0 # where all recursive calls eventually stop 
       left = max_height(node.left) # <- these are the recursive calls: 
       right = max_height(node.right) # <- function x is called inside function x 
       return max(left, right) + 1 # max here, not max_height 
   

これは単にあなたがリンクされ、質問にthis answerの、より詳細なバージョンであることに注意してください。

Answer 2

すべての回答は正しかったが、私はクラス内に書いている間はほとんど問題にはいかなかった。

コードはこのようになっています。私はこれが役に立ちそうです。

class Tree(object): 
     def height(self, root): 
      if root == None: #root == None 
       return 0 
      else: 
       return 1 + max(self.height(root->left), self.height(root->left)) 
t = Tree() 
t.height(t)