LeetCode94二叉树中序遍历：递归代码报错原因及递归原理咨询

• 缩进导致逻辑不可达：你在if root==None:代码块中第一行就写了return None，这会直接退出函数，后面的递归调用语句永远不会执行。而且当root不为空时，这些递归代码因为缩进在if块内，根本不会被触发，最终list1始终是空列表，无法得到正确遍历结果。
• 递归调用方式错误：作为类的成员方法，递归调用必须使用self.inorderTraversal，直接写inorderTraversal会触发“未定义函数”的报错。
• 局部列表无法共享：即使修正了缩进，每次递归调用inorderTraversal都会新建独立的list1局部变量，递归返回的结果不会合并到最初的列表中，最终还是只能得到空列表。
• 返回值不符合题目要求：题目要求返回List[int]类型，当root为空时你返回None，会导致类型不匹配错误，正确处理应该返回空列表[]。

递归的核心是把大问题拆解成完全相同的小问题，直到遇到终止条件再回溯处理，二叉树的遍历天生适合用递归，因为每个子树本身就是一棵独立的二叉树。

中序遍历的递归逻辑拆解 #

中序遍历的规则是：左子树遍历 → 访问当前节点 → 右子树遍历，终止条件是当前节点为None（空树不需要遍历）。

拿一个简单二叉树举例：

1
     \
      2
     /
    3

我们一步步推演递归执行过程：

1. 调用inorderTraversal(1)：
   • 先处理左子树1.left（为None），触发终止条件，直接返回。
   • 执行list1.append(1.val)，列表变为[1]。
   • 处理右子树1.right（节点2），调用inorderTraversal(2)。
2. 调用inorderTraversal(2)：
   • 处理左子树2.left（节点3），调用inorderTraversal(3)。
3. 调用inorderTraversal(3)：
   • 处理左子树3.left（None），终止返回。
   • 执行list1.append(3.val)，列表变为[1,3]。
   • 处理右子树3.right（None），终止返回。
4. 回到inorderTraversal(2)的执行：
   • 执行list1.append(2.val)，列表变为[1,3,2]。
   • 处理右子树2.right（None），终止返回。
5. 回到最初的inorderTraversal(1)，返回最终列表[1,3,2]。

递归栈的本质 #

递归的执行依赖调用栈：每次发起递归调用时，当前函数的状态（比如当前节点、执行到哪一行代码）会被压入栈中；当遇到终止条件时，函数开始从栈顶逐个回溯，执行剩余的代码（比如添加节点值）。你可以把这个过程想象成“钻到最底层的左子树，再一步步往回爬，同时把路过的节点值加入列表”。

复杂递归问题的推演技巧 #

面对复杂二叉树时，不用纠结每一步的细节，只需要抓住两个关键点：

• 终止条件：明确什么时候停止递归（比如节点为空）。
• 单次递归的职责：明确当前节点需要做什么（中序就是先处理左，再处理自己，最后处理右）。
  把每个子树都当成独立的小问题，相信递归能正确处理子问题，再把结果组合起来，这就是递归的“分治思想”。

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