LeetCode递归函数空间复杂度疑问：O(n)还是O(n²)？

这段代码的空间复杂度是O(n)（n为二叉树的节点总数），具体拆解如下：

• 空间复杂度的核心判断依据是同一时刻内存占用的最大值，而非所有调用的累计消耗。
• 代码中的两个递归函数pathSum和traverse是串行执行的：
  1. 调用某个节点的pathSum时，会先完整执行完该节点的traverse递归链（此时栈内是traverse的调用栈，最大深度等于当前子树的深度），等traverse执行完毕、栈完全清空后，才会递归调用左/右子树的pathSum。
  2. pathSum自身的递归链，最大深度也等于树的深度（比如二叉树退化成单链表时，深度就是n）。
• 最坏场景下（链式二叉树），不管是traverse还是pathSum的递归栈，最大占用空间都是O(n)，两者不会同时叠加产生更大的内存消耗。
• 全局变量count和targetSum属于常数级空间，不影响整体复杂度。

为什么不会是O(n²)？因为O(n²)需要同一时刻栈内同时存在n层pathSum和n层traverse的调用，但实际中这两个递归栈永远不会共存——traverse执行时，当前pathSum调用处于等待状态，但traverse的栈独立且执行完就释放，不会和后续的pathSum递归栈叠加。

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