二叉搜索树中序遍历递归调用栈变量追踪逻辑咨询

问题背景 #

• 学习递归与回溯逻辑过程中，针对数组[10, 14, 19, 27, 31, 35, 42]构建的二叉搜索树（BST），编写了三种中序遍历递归实现：
  • 方案1：结果列表res定义在递归辅助函数外部，调用栈逻辑可理解
  • 方案2：遍历过程直接打印节点值，调用栈逻辑可理解
  • 方案3：递归函数内部初始化res列表，通过「接收左子树返回结果→追加当前节点值→拼接右子树返回结果」的形式返回最终值，无法理清各层递归中res的状态追踪逻辑

备注：示例中三个同名的inorderTraversalRecursive方法仅作对比演示，实际运行时不会重复定义同名方法。

相关实现代码 #

class Node:

    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
        node = Node(data)
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = node
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = node
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def printTree(self):
        if self.left:
            self.left.printTree()
        print(self.data)
        if self.right:
            self.right.printTree()

    # 方案1：res定义在辅助函数外部
    def inorderTraversalRecursive(self, root):
        res = []

        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.data)
            inorder(root.right)

        inorder(root)
        return res

    # 方案2：直接打印节点值
    def inorderTraversalRecursive(self, root):
        if root is None:
            return
        self.inorderTraversalRecursive(root.left)
        print(root.data, end=' ')
        self.inorderTraversalRecursive(root.right)

    # 方案3：递归内部初始化res，通过返回值拼接结果
    def inorderTraversalRecursive(self, root):
        res = []
        if root:
            res = self.inorderTraversalRecursive(root.left)
            res.append(root.data)
            res = res + self.inorderTraversalRecursive(root.right)
        return res


# 构建BST
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversalRecursive(root))

构建完成的BST结构如下：

27
      /    \
    14      35
   /  \    /  \
 10   19  31  42

方案3核心规则 #

先明确两个核心前提，再走调用流程就不会混乱：

• 每一层递归调用对应调用栈中一个独立栈帧，栈帧内的局部变量res是当前层独有的，和其他层的同名变量完全隔离，不存在跨层共享
• 递归终止条件：传入节点为None时，直接返回空列表[]

完整调用栈执行流程 #

我们从最外层调用root.inorderTraversalRecursive(root)（传入27节点）开始，按入栈、暂停、返回、出栈的顺序逐轮拆解：

1. 第1层入栈：传入节点27
   • 初始化本层res = []
   • 检测到节点存在，首先执行左子树遍历，传入14节点触发第2层调用，当前层暂停，等待返回结果
2. 第2层入栈：传入节点14
   • 初始化本层res = []
   • 检测到节点存在，执行左子树遍历，传入10节点触发第3层调用，当前层暂停
3. 第3层入栈：传入节点10
   • 初始化本层res = []
   • 检测到节点存在，执行左子树遍历，传入10的左子节点（None）触发第4层调用，当前层暂停
4. 第4层入栈：传入None
   • 初始化本层res = []
   • 检测到节点不存在，直接返回[]，本层出栈
5. 回到第3层（节点10）恢复执行
   • 接收左子树返回值[]，赋值给本层res，此时res = []
   • 追加当前节点值10，res = [10]
   • 执行右子树遍历，传入10的右子节点（None）触发第5层调用，当前层暂停
6. 第5层入栈：传入None，直接返回[]，本层出栈
7. 回到第3层（节点10）恢复执行
   • 接收右子树返回值[]，拼接后res = [10] + [] = [10]
   • 返回[10]，本层出栈
8. 回到第2层（节点14）恢复执行
   • 接收左子树返回值[10]，赋值给本层res，此时res = [10]
   • 追加当前节点值14，res = [10, 14]
   • 执行右子树遍历，传入14的右子节点19触发第6层调用，当前层暂停
9. 第6层入栈：传入节点19
   • 初始化本层res = []
   • 执行左子树遍历，传入19的左子节点（None）触发第7层调用
10. 第7层入栈：传入None，返回[]，本层出栈
11. 回到第6层（节点19）恢复执行
    • 接收左子树返回值[]，赋值给res，追加当前节点值19，res = [19]
    • 执行右子树遍历，传入19的右子节点（None）触发第8层调用
12. 第8层入栈：传入None，返回[]，本层出栈
13. 回到第6层（节点19）恢复执行
    • 拼接右子树返回值[]，res = [19] + [] = [19]
    • 返回[19]，本层出栈
14. 回到第2层（节点14）恢复执行
    • 接收右子树返回值[19]，拼接后res = [10,14] + [19] = [10,14,19]
    • 返回该列表，本层出栈
15. 回到第1层（节点27）恢复执行
    • 接收左子树返回值[10,14,19]，赋值给本层res，追加当前节点值27，res = [10,14,19,27]
    • 执行右子树遍历，传入27的右子节点35触发第9层调用，当前层暂停
16. 第9层入栈：传入节点35
    • 初始化本层res = []
    • 执行左子树遍历，传入35的左子节点31触发第10层调用
17. 第10层入栈：传入节点31
    • 初始化res = []，左右子节点均为None，遍历完成后返回[31]，本层出栈
18. 回到第9层（节点35）恢复执行
    • 接收左子树返回值[31]，赋值给res，追加当前节点值35，res = [31,35]
    • 执行右子树遍历，传入35的右子节点42触发第11层调用
19. 第11层入栈：传入节点42
    • 初始化res = []，左右子节点均为None，遍历完成后返回[42]，本层出栈
20. 回到第9层（节点35）恢复执行
    • 拼接右子树返回值[42]，res = [31,35] + [42] = [31,35,42]
    • 返回该列表，本层出栈
21. 回到第1层（节点27）恢复执行
    • 接收右子树返回值[31,35,42]，拼接后res = [10,14,19,27] + [31,35,42] = [10,14,19,27,31,35,42]
    • 返回最终结果，本层出栈，整个递归流程结束

关键认知 #

• 递归的局部变量不需要跨层追踪：每个栈帧的生命周期和对应函数调用完全绑定，函数返回后栈帧销毁，局部变量随之回收，不会出现变量混淆的问题
• 方案3是无共享状态的纯函数式递归：前两种方案依赖外部共享的res列表、标准输出流存储结果，方案3完全通过返回值逐层传递子树遍历结果，没有副作用，逻辑上更贴近递归“分治求解子问题”的本质
• 空节点返回空列表是拼接逻辑成立的核心：空节点不存在有效值，返回空列表在拼接时不会改变原有结果，同时作为递归终止条件避免无限调用

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