递归和二叉树

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)