python - 以下二叉搜索树方法的大O是多少

Question

我知道这可能是微不足道的，但我只是想确定一下。我相信它的运行时间最多为 O(n)。我的理由是，在这个递归方法中，每个节点都会返回一个高度值。或者换句话说，我们将访问树中的每个节点一次。

    def height(self):
        if self.is_empty():
            return 0
        else:
            left_max = self._left.height()
            right_max = self._right.height()
            return max(left_max, right_max) + 1

标签： pythonrecursiontime-complexitybinary-search-treespace-complexity

Answer 1

• 您正在树上执行 DFS 遍历，所有节点只会被访问一次。
• 所以显然它只需要 O(N) 的时间。