search - 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)。