遞歸和二叉樹

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來獲得長度，但我得到一個錯誤。我想到了三種可能性：

1）我誤解了基本案例的概念，實際上我沒有基本案例。

2）我沒有正確地分隔Python代碼。

3）我沒有遞歸地獲得BST的高度，而是樹的寬度，這影響了以後的計算。

我知道它與這個問題類似，但主要的區別是我真的試圖使用遞歸，其中另一個問題使用迭代，只是將其稱爲遞歸。 how to find the height of a node in binary tree recursively

Answer 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)