java - 找到树中节点深度的更好方法

Question

我想计算树的深度 我在下面写了代码

我的问题是:

1. 这段代码的顺序是什么？是O(n)吗[n是树节点数]
2. 您认为还有其他更好更快的方法吗？

提前致谢

public int height(Node n)
{
    if(n == null)
        return 0;
    return 1 + Math.max(height(n.left), height(n.right));

}

Answer 1

无论您拥有什么类型的树，它的复杂度都是 O(n)，因为您要访问每个节点来建立最大深度。

唯一更有效的方法是将有关树的额外信息存储在某处。如果它是平衡的，您就可以根据节点数量知道最大高度。

或者，您可以缓存该信息。有两个额外的变量 depth 和 dirty 并最初将 dirty 设置为 true:

• 当调用者请求深度并且 dirty 为 true 时，调用您的函数来计算它，但将其存储到 深度 中并设置 dirty > 为假。
• 当调用者请求深度且 dirty 为 false 时，只需返回深度。
• 每当树的结构发生更改(插入或删除节点)时，请将 dirty 设置为 true。