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

Question

给定一个二进制搜索树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) )

然而，我注意到它的复杂性呈指数级增长，因此当我们有一棵深树时，它的表现应该非常糟糕。有没有更快的算法可以做到这一点？

Answer 1

如果将高度存储为Node对象中的字段，则可以在向树中添加节点时添加1（在移除过程中减去）。

这将使获取任何节点高度的操作时间恒定，但这会给添加/删除操作增加一些额外的复杂性。

Answer 2

这是对@cricket_007在他的回答中提到的内容的扩展。

因此，如果您执行( 1 + max(height_left,height_right) )，您最终必须访问每个节点，这本质上是一个O（N）操作。对于具有平衡树的平均情况，您将看到类似T(n) = 2T(n/2) + Θ(1)的内容。

现在，如果可以存储某个节点的高度，则可以将其改进为时间O（1）。在这种情况下，树的高度将等于根的高度。因此，您需要对insert(value)方法进行修改。在开始时，根的默认高度为0。将为要添加的节点指定高度0。对于尝试添加此新节点时遇到的每个节点，如果需要，请将node.height增加1，并确保将其设置为1+max（左子节点的高度，右子节点的身高）。因此，height函数将简单地返回node.height，从而允许恒定时间。插入的时间复杂性也不会改变；我们只需要一些额外的空间来存储n整数值，其中n是节点的数量。

下面展示的内容是为了理解我想说的内容。

          5 [0]
- insert 2 [increase height of root by 1]
          5 [1]
         / 
        /   
   [0] 2 
- insert 1 [increase height of node 2 by 1, increase height of node 5 by 1]
          5 [2]
         / 
        /   
   [1] 2    
      / 
     /   
[0] 1  
- insert 3 [new height of node 2 = 1 + max(height of node 1, height of node 3) 
                                 = 1 + 0 = 1; height of node 5 also does not change]
          5 [2]
         / 
        /   
   [1] 2     
      / 
     /   
[0] 1     3 [0]
- insert 6 [new height of node 5 = 1 + max(height of node 2, height of node 6) 
                                 = 1 + 1 = 2]
          5 [2]
         / 
        /   
   [1] 2     6 [0]
      / 
     /   
[0] 1     3 [0]