algorithm - 如何以较低的复杂度计算二叉树的深度？

给定一个二叉搜索树t，使用递归很容易得到它的深度，如下所示：

def node_height(t):
    if t.left.value == None and t.right.value == None:
        return 1
    else:
        height_left = t.left.node_height()
        height_right = t.right.node_height()
        return ( 1 + max(height_left,height_right) )

然而，我注意到它的复杂度呈指数增长，因此当我们有一棵深树时，它应该执行得非常糟糕。有没有更快的算法来做这个？

最佳答案

如果将高度存储为节点对象中的字段，则可以在向树中添加节点时添加1（并在移除期间减去）。
这将使操作保持恒定的时间来获取任何节点的高度，但是它在添加/移除操作中增加了一些额外的复杂性。

关于algorithm - 如何以较低的复杂度计算二叉树的深度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37106511/