python - 递归和二叉树

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 的更详细版本。到您链接的问题。