LeetCode94二叉树中序遍历解法的时间/空间复杂度计算及递归讲解

时间复杂度计算 #

递归的时间复杂度本质是所有递归调用的总次数 × 单次调用的时间开销：

• 先统计递归函数被调用的总次数，包括触发终止条件的调用（比如空节点调用）；
• 再看每次调用内执行的操作复杂度，将总次数与单次开销相乘后取渐近复杂度。

空间复杂度计算 #

递归的空间复杂度要考虑两部分：

1. 递归调用栈空间：每次递归调用时，系统会在栈中保存当前函数的上下文（参数、局部变量、返回地址等），这部分空间的大小取决于递归调用的深度（即递归栈的最大层数）；
2. 额外辅助空间：比如存储结果的数组、临时哈希表等，这部分需要单独统计。

先给出典型的递归中序遍历代码：

def inorderTraversal(root):
    res = []
    def helper(node):
        if not node:
            return
        helper(node.left)
        res.append(node.val)
        helper(node.right)
    helper(root)
    return res

时间复杂度分析 #

• 每个二叉树节点会被helper函数访问一次，同时每个节点的左右空指针也会触发一次helper调用（二叉树的空指针总数为n+1，n是节点总数）；
• 每次helper调用里的操作（空节点直接返回、非空节点的递归调用和值存入数组）都是O(1)复杂度；
• 总调用次数为n + (n+1) = 2n+1次，总时间开销的渐近复杂度为O(n)，你的推测是正确的。

空间复杂度分析 #

你的O(1)推测是错误的，原因如下：

1. 递归调用栈空间：递归栈的深度等于二叉树的高度h。如果是平衡二叉树，h=logn，栈空间复杂度为O(logn)；如果是极端链式二叉树（比如所有节点只有左孩子），h=n，栈空间复杂度为O(n)；
2. 结果数组空间：用来存储遍历结果的res数组需要占用O(n)空间，但LeetCode题目中通常将输出结果的空间不计入算法的额外空间复杂度；

• 综上，该递归解法的空间复杂度为O(h)（h为树的高度），最坏情况O(n)，平均情况O(logn)。

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