c++ - 树的高度的复杂性

Question

考虑代码:

int Tree::height(tree *node) {
    if (!node) return -1;

    return 1 + max(height(node->left), height(node->right));
}

这个方法的复杂度是多少？ O(n) 还是 O(log(n))？

我认为它是 O(n) ，因为在最坏的情况下我们会检查所有节点，不是吗？

您能举一个更好的实现示例吗？

谢谢

Answer 1

我认为您正在检查所有情况下的所有节点，而不仅仅是最坏的情况。所以是的，O(N)。