递归函数内部栈帧机制探究：二叉树最大深度计算场景

问题背景 #

我想理解递归函数调用时系统调用栈的内部工作机制，重点聚焦在后序遍历计算二叉树最大深度的场景。我已经了解基于栈的迭代实现，但希望找到更贴近系统内部调用逻辑的实现方式。

测试用的二叉树结构 #

1
   / \
  2   3
 / \
4   5

递归实现代码 #

from typing import Optional, Union, Literal

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root: Optional[TreeNode]) -> int:
    def dfs_postorder(node: TreeNode) -> Union[int, Literal[0]]:
        if not node:
            return 0

        left_depth = dfs_postorder(node.left)
        right_depth = dfs_postorder(node.right)
        return max(left_depth, right_depth) + 1

    return dfs_postorder(root)

核心疑问 #

我知道递归时会先调用根节点1，接着是左子节点2，再到左子节点4，直到叶子节点，每一步都会向调用栈添加栈帧。但我对右子节点何时被加入调用栈有疑惑：

• 我理解的逻辑是：处理完所有左子节点后才会处理右子节点，比如首次调用根节点1后，下一个调用是左子节点2，此时调用栈应该是：

  [(1, "未处理完"), (2, "待处理")]
  

  其中"待处理"表示节点的左右子节点还没遍历，"未处理完"表示节点已经入栈但还没执行完后续逻辑（比如还没调用右子节点）。
• 但有人告诉我此时栈中还会包含右子节点3的栈帧，即：

  [(1, "未处理完"), (3, "待处理"), (2, "待处理")]
  

  这让我困惑，想知道这种场景下系统调用栈的实际工作机制到底是怎样的？

系统调用栈的实际工作流程 #

首先明确：你最初的理解是正确的，对方的说法错误。系统调用栈的行为完全遵循代码的执行顺序，不会提前将未触发的函数调用压入栈中。

我们一步步拆解递归调用的栈变化（栈帧用(节点值, 当前执行到的代码行)来标记）：

1. 初始调用dfs_postorder(1)，栈帧(1, 执行到第7行)被压入栈，此时栈：[(1, 第7行)]
2. 执行到left_depth = dfs_postorder(node.left)，即调用dfs_postorder(2)，栈帧(2, 执行到第7行)压入栈，此时栈：[(1, 第7行), (2, 第7行)]
3. 同样，执行dfs_postorder(2)的第7行，调用dfs_postorder(4)，栈帧(4, 执行到第7行)压入栈，此时栈：[(1, 第7行), (2, 第7行), (4, 第7行)]
4. 执行dfs_postorder(4)的第7行，调用dfs_postorder(None)，触发if not node直接返回0，这个临时栈帧执行完毕后立即弹出，栈回到[(1, 第7行), (2, 第7行), (4, 第7行)]
5. 栈帧4现在执行第8行：right_depth = dfs_postorder(node.right)，调用dfs_postorder(None)，同样返回0，临时栈帧弹出，栈不变
6. 栈帧4执行第9行：return max(0,0)+1，返回1，栈帧4弹出，栈回到[(1, 第7行), (2, 第7行)]，此时left_depth（对应节点2的左子树）的值为1
7. 栈帧2执行第8行：right_depth = dfs_postorder(5)，栈帧(5, 执行到第7行)压入栈，此时栈：[(1, 第7行), (2, 第7行), (5, 第7行)]
8. 重复步骤4-6的逻辑，节点5的左右子节点都是None，最终返回1，栈帧5弹出，栈回到[(1, 第7行), (2, 第7行)]，right_depth（节点2的右子树）的值为1
9. 栈帧2执行第9行：return max(1,1)+1，返回2，栈帧2弹出，栈回到[(1, 第7行)]，此时left_depth（节点1的左子树）的值为2
10. 直到这里，才会执行栈帧1的第8行：right_depth = dfs_postorder(3)，此时栈帧(3, 执行到第7行)才会被压入栈，栈变为[(1, 第7行), (3, 第7行)]

总结：右子节点的栈帧只会在当前节点的左子树递归完全执行完毕后，才会被创建并压入调用栈，绝不会提前出现在栈中。对方的说法混淆了递归调用栈和某些迭代实现的栈逻辑。

对比LeetCode的迭代栈实现 #

你提供的LeetCode迭代代码是前序遍历的变种，它的栈逻辑和系统递归栈完全不同：

from typing import Union, Literal

class BinaryTreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxDepth_stack(self, root: BinaryTreeNode) -> Union[int, Literal[0]]:
        if not root:
            return 0

        stack = [(1, root)] # 栈存储(深度, 节点)元组
        max_depth = 0
        while stack:
            depth, node = stack.pop()
            if node: # 如果节点不为空
                # 更新最大深度
                max_depth = max(max_depth, depth)
                # 先压入左子节点（因为栈是后进先出，所以实际会先处理右子节点）
                stack.append((depth + 1, node.left))
                # 再压入右子节点
                stack.append((depth + 1, node.right))
        return max_depth

这个迭代方案为了模拟遍历，会一次性把当前节点的左右子节点都压入栈，但这是人为设计的迭代逻辑，和系统递归栈的"按需创建栈帧"完全不是一回事。系统递归栈只会在执行到函数调用语句时，才会创建对应的栈帧并压入。

贴近系统递归栈的迭代实现参考 #

如果要写一个更贴近系统递归栈逻辑的迭代实现，需要记录每个节点的状态（是否已经处理过左子树），示例代码如下：

def maxDepth_simulate_recursion(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    stack = [(root, False, 0, 0)]  # (节点, 是否已处理左子树, 左子树深度, 右子树深度)
    max_depth = 0
    while stack:
        node, processed_left, left_d, right_d = stack.pop()
        if not processed_left:
            # 未处理左子树，先把当前节点标记为待处理右子树，再压入左子节点
            stack.append((node, True, left_d, right_d))
            if node.left:
                stack.append((node.left, False, 0, 0))
        else:
            # 已处理左子树，现在处理右子树
            if node.right:
                stack.append((node, True, left_d, right_d))
                stack.append((node.right, False, 0, 0))
            else:
                # 左右子树都处理完，计算当前节点深度
                current_depth = max(left_d, right_d) + 1
                max_depth = max(max_depth, current_depth)
                # 如果栈不为空，把当前深度传递给父节点的左/右深度
                if stack:
                    parent_node, parent_processed, parent_left_d, parent_right_d = stack[-1]
                    if not parent_processed:
                        # 当前是父节点的左子树，更新父节点的左深度
                        stack[-1] = (parent_node, parent_processed, current_depth, parent_right_d)
                    else:
                        # 当前是父节点的右子树，更新父节点的右深度
                        stack[-1] = (parent_node, parent_processed, parent_left_d, current_depth)
    return max_depth

这个实现通过标记节点是否处理过左子树，完全模拟了递归时系统栈的"先处理左子树，再处理右子树，最后计算当前节点值"的流程。

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