二叉树高度 - 该算法在 python 中如何工作？

Question

我偶然发现了这个算法来计算二叉树的高度。有谁能解释它是如何工作的？具体来说，我对 max 函数内部的递归调用感到困惑。每次迭代的最大比较是多少？如何在不导致 TypeError 的情况下将输出加到 1？谢谢！

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

Answer 1

Specifically, I'm confused about the recursive calls inside the max function. What is max comparing on each iteration and how is the output able to be added to 1 without causing a TypeError?

您调用了一个函数两次，并将这两次函数调用的 return 值传递给 max。因此，max 正在比较此函数 returns 的任何内容。

如果不清楚，让我们分解一下 one-liner:

left_height = get_height(root.left)
right_height = get_height(root.right)
max_height = max(left_height, right_height)
return 1 + max_height

由于我们调用的函数总是 return 是一个整数，max 正在比较两个整数，这会给出两个整数中较大的一个。这是我们显然可以加 1 的东西。

换句话说，树的高度比哪个子树的高度高1。

你可能认为我在那里作弊。我如何才能证明该函数总是 return 是一个整数，而我不得不假设它来证明它？

关键是递归是归纳的。如果你不太懂数学，这是一种奇特的说法：

如果基本情况总是 return 是一个整数，
并且递归总是调用较小的情况
如果我们总是return一个整数，只要所有较小的情况return一个整数
那么我们总是return一个整数。

第一部分很简单：如果是None，我们return0.

第二部分来自树的定义：树的左分支和树的右分支总是树的更小的子树。（这对于循环图来说并非如此，其中 root.left 可能是 root 或其祖父母。）

第三部分是对前半部分答案的解释

我们完成了。

Answer 2

在代码中添加一些行将有助于弄清楚发生了什么。
这里有一个 class 代表一棵树。

class Tree:
    def __init__(self,id,left=None,right=None):
        self.id = id
        self.left = left
        self.right = right

还有一个计算高度的函数。

def get_height(root):
    if root is None: 
        return 0

    my_height = 1 + max(get_height(root.left), get_height(root.right))
    print("id :{} height: {}".format(root.id,my_height))
    return my_height

t = Tree(1,Tree(2,Tree(4),Tree(5)),Tree(3))

t可以看到如下

当调用 get_height(t) 时，这是输出：

id :4 height: 1
id :5 height: 1
id :2 height: 2
id :3 height: 1
id :1 height: 3

调用从根开始，直到到达叶节点后，函数将被调用 None。
假设已经到达一片叶子（例如，节点 4）。节点 4 上 get_height() 的结果将是 1 + max(get_height(None),get_height(None)) = 1 + max(0,0) =1.
节点 4 因此 returns 1. 调用者（节点 4 的父节点，即节点 2）将从 Node 4 获得 1 并从 Node 5 获得 1 .
因此它会得出它的高度是1+max(1,1)=2和return这个值给父节点。
以同样的方式，节点 1（根）将从 Node 2 获得 2 并从 Node 3 获得 1 并将其高度计算为 1+max(1,2)=3.
Tree的高度为3，作为根的高度为3。

二叉树高度 - 该算法在 python 中如何工作？

Binary tree height - how does this algorithm work in python?

python

recursion

binary-tree