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

Question

我不是CS的学生，所以这不是家庭作业。我正在尝试自己学习这些东西，但我想确保自己一路上不养成不良习惯。

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

我的身高是指这张图片：

这棵树的高度是3。

这是我想到的python：

def height(node):

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

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

    #if has right, incriment 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)