关于含独立辅助空间的递归函数空间复杂度的疑问

先看你给出的示例代码：

def dfs(root, seen):
  if not root:
    return seen
  
  seen.add(root)
  new_set = set(seen)

  dfs(root.left, new_set)
  dfs(root.right, new_set)

你的判断完全正确，这个递归函数的辅助空间复杂度确实是O(H²)，具体分析如下：

• 递归调用栈的空间：最坏情况（比如树是单链结构）下，调用栈深度为H（树的高度），每个栈帧本身占用常数空间，这部分是O(H)。
• 集合的空间开销：每个递归调用都会创建一个新的new_set，它是当前seen的完整拷贝。沿着递归的最深路径，每往下一层，集合就会新增一个节点元素，因此栈上同时存在的H个调用对应的集合，元素数量分别为1、2、…、H。这些集合的总元素数是1+2+…+H = H*(H+1)/2，属于O(H²)的量级。

两者相加后，整体辅助空间复杂度由占主导的O(H²)决定。

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