我想计算一棵树的深度
我在下面写了代码
我的问题是：
该代码的顺序是什么？是O（n）[n是树节点数]
您认为还有其他更好更好的方法吗？
提前致谢
public int height(Node n)
{
if(n == null)
return 0;
return 1 + Math.max(height(n.left), height(n.right));
}
最佳答案
它是O（n），与您拥有的树的类型无关，因为您要访问每个节点来确定最大深度。
唯一有效的方法是将有关树的额外信息存储在某个地方。如果它是平衡的，则根据节点数知道最大高度。
或者，您可以缓存信息。有两个额外的变量depth和dirty，最初将dirty设置为true：
当调用者请求深度且dirty为true时，调用您的函数以进行计算，但将其存储在depth中并将dirty设置为false。
当呼叫者请求深度并且dirty为假时，只需返回depth。
每当更改树的结构（插入或删除节点）时，将dirty设置为true。