求左右子树的最大高度

Question

我想实现以下功能：

    def get_height(root, d):
        
        if root.left:
            left = get_height(root.left, d + 1)
        if root.right:
            right = get_height(root.right, d + 1)

思路很简单：对于给定的节点，我想要它的左右子树的最大高度。代码显然还没有完成。我正在寻找一种干净的方法来完成上面的代码，所以 return 值是最大值。左右子树的高度。

Answer 1

要完成方法，您需要添加 return 并确保基本情况有效。基本情况是节点是叶子时。因此，您需要为 left 和 right:

提供默认值

def get_height(root, d):
    left = d
    right = d
    if root.left:
        left = get_height(root.left, d + 1)
    if root.right:
        right = get_height(root.right, d + 1)
    return max(left, right)

但这不是最佳做法。您应该避免使用额外的 d 参数。你可以不用，让每个调用 return that 节点的高度，而不必知道有关父节点的任何信息。进行递归调用时，caller 可以将 returned 值加 1：

def get_height(root):
    left = 0
    right = 0
    if root.left:
        left = get_height(root.left) + 1
    if root.right:
        right = get_height(root.right) + 1
    return max(left, right)

您还可以将基本案例更进一步，因此只需要一个 if：

def get_height(root):
    if not root:
        return -1
    return max(get_height(root.left), get_height(root.right)) + 1

求左右子树的最大高度

Finding the maximum height of left and right subtree

binary-tree