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

我正试图找出如何用二叉树的高度标记每个节点。我可以这样做效率低下如下：

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）。
我想我想做的是“自下而上”的工作：计算一个节点的子节点的高度（如果还没有存储的话），并用它来设置有问题的节点的高度。
我有点困惑。
仅供参考，这不是硬件问题。
谢谢！

最佳答案

你不需要getHeight。只需返回每个子树的高度，就可以在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