二叉搜索树中序遍历代码时间复杂度疑问：为何不是O(n²)？

先看你给出的代码：

def inorder(r):
   return inorder(r.left) + [r.val] + inorder(r.right) if r else []

你的疑问完全正确——这个写法的时间复杂度并不是严格的O(n)，你注意到列表加法的开销是关键，具体原因如下：

• Python里的列表加法a + b会创建新列表，把两个原列表的元素全部复制进去，时间开销等于两个列表的长度之和。
• 针对这个递归逻辑：
  • 如果是极端不平衡的BST（比如所有节点只有右子树，结构像链表），每次递归都要把当前节点的[r.val]和右子树返回的长列表拼接。比如第k个节点（从根往下数），拼接操作要复制k个元素，总操作次数就是1+2+3+...+n = O(n²)，时间复杂度是平方级的。
  • 如果是平衡BST，每个节点的拼接操作涉及的列表长度和所在层的总节点数相关，整个树有O(log n)层，每层总拼接操作是O(n)，所以总时间复杂度是O(n log n)，也不是线性的。

那些说时间复杂度是O(n)的说法，通常只算了节点访问次数（每个节点确实只被访问一次），但忽略了列表拼接带来的额外复制开销。如果要实现真正O(n)时间的中序遍历，应该用可变列表收集结果，比如：

def inorder(r):
    res = []
    def traverse(node):
        if node:
            traverse(node.left)
            res.append(node.val)
            traverse(node.right)
    traverse(r)
    return res

这种写法里append是均摊O(1)的操作，全程没有额外的列表复制，才是严格的线性时间复杂度。

内容的提问来源于stack exchange，提问作者robt