BST最糟糕的时间复杂度(遍历它)

Question

考虑N节点的二叉搜索树的后序遍历的时间复杂度。我知道在一般情况下，O(N)需要访问所有节点，但是当BST是一个列表时，最坏情况下的复杂度是多少?我认为它需要O(N^2)，因为它将穿越N节点到达终点，N节点回到起点。这意味着N*N = N^2，所以我认为它是O(N^2)。对吗?

Answer 1

在你的"最坏情况"情况下(坦率地说，我不理解)是N + N = O(N)，而不是N * N = O(N^2)。