algorithm - 有效地在二叉树中标记高度

Question

我想弄清楚如何用高度标记二叉树中的每个节点。我可以按如下方式低效地执行此操作:

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

def labelHeights(root):
    if root is None:
        return
    root.height = getHeight(root)
    labelHeights(root.left)
    labelHeights(root.right)

但是这样会浪费很多时间，而且在二叉树的节点数上是O(n^2)。

我想我想“自下而上”地工作:计算节点子节点的高度(如果尚未存储)并使用它来设置相关节点的高度。

我有点难过

仅供引用，这不是硬件问题。

谢谢!

Answer 1

您不需要 getHeight。您只需让 labelHeights 返回每个子树的高度，就可以在 O(N) 中以深度优先的方式执行此操作。例如

def labelHeights(n):
    if n is None:
        return 0
    lh = labelHeights(n.left)
    rh = labelHeights(n.right)
    n.height = max(lh, rh) + 1
    return n.height