这是获取二叉树高度的好方法吗？

Question

我不是 CS 学生，所以这不是家庭作业。我正在尝试自己学习这些东西，但我想确保自己没有在学习过程中养成坏习惯。

基本上，我有一个经典的二叉树，我想计算树的高度（或深度）。

我说的身高是这个图：

这棵树的高度是3。

这是我想出的python：

def height(node):

    #highest one of these two will be returned
    i_left = 0
    i_right = 0

    #if has left, increment and recursively move left
    if node.hasleft():
        i_left += height(node.left)
        i_left += 1

    #if has right, increment and recursively move right
    if node.hasright():
        i_right += height(node.right)
        i_right += 1

    #return the higher value
    if i_right <= i_left:
        return i_left    
    return i_right

这个解决方案很有效，我有点喜欢它，因为它很简单，没有很多抽象的东西需要你思考。但是，我确实想知道这是否应该这样做。有什么方法可以改进它，或者有更容易接受的实现高度函数的方法吗？

Answer 1

如果有子节点，您的代码只会将左节点或右节点的高度加1。即使没有子节点，也需要为当前节点加 1。所以它不应该在 if 块中。

def height(node):

    #if has left, recursively move left
    if node.hasleft():
        i_left = height(node.left)
    else:
        i_left = 0

    #if has right, recursively move right
    if node.hasright():
        i_right = height(node.right)
    else:
        i_right = 0

    #return the higher value, plus 1 for the current node.
    return 1 + max(i_left, i_right)

Answer 2

你的整体算法是最好的方法。

您无法知道哪个分支最长，因此唯一的方法是检查每条路径并找到最大值。您的递归结构似乎是非常经典的树结构！

Answer 3

你的算法的核心思想是合理和正确的；必须递归调用左右子树，加1.

假设你的 node.left 和 node.right 属性分别是 None 当没有左子树或右子树时，可以通过只检查一次检查当前是否节点存在，而不是两次检查以查看其每个子节点是否存在。这意味着输入有时是 None，在这种情况下，正确的 return 值为 -1，因此叶节点的高度将为 0。

def height(node):
    if node is None:
        return -1
    else:
        i_left = height(node.left)
        i_right = height(node.right)
        return 1 + max(i_left, i_right)

或者，如果您是单线的粉丝：

def height(node):
    return -1 if node is None else 1 + max(height(node.left), height(node.right))

这里按照height的the usual definition作为从根节点到最长路径的边数，这样一棵有一个节点的树的高度为0。如果定义height为节点数那条路径，因此单节点树的高度为 1，然后只需将基本情况更改为 return 0 而不是 return -1.

这是获取二叉树高度的好方法吗？

Is this a good way to get the height of a binary tree?

python

algorithm

tree

search

binary-tree