中序遍历函数返回None问题排查：输入[1,2,3]未获预期输出[3,1,2]

我尝试通过中序遍历返回列表，以下是我的代码。当输入为[1,2,3]时，预期输出应为[3,1,2]，但实际返回值为None。请帮忙指出代码中的问题，谢谢。

你的代码如下：

def inorderTraversal(currentNode,output=None):
    if output==None:
        output=[]
    if currentNode.left:
        return inorderTraversal(currentNode.left,output)
    return output.append(currentNode.data)
    if currentNode.right:
        return inorderTraversal(currentNode.right,output)

问题出在这两个关键地方： #

• 过早的return直接导致返回None，还阻断了后续逻辑
  你在执行output.append(currentNode.data)后直接return了，但list.append()方法本身的返回值就是None，这就是你最终得到None的直接原因。而且这个return会直接跳出函数，后面遍历右子树的代码根本没机会执行。

• 左子树遍历后的return完全打乱了遍历顺序
  中序遍历的核心顺序是「左子树 → 当前节点 → 右子树」，但你在遍历左子树时就直接return inorderTraversal(...)，这会导致左子树遍历完成后直接返回，完全跳过了当前节点的处理和右子树的遍历，逻辑完全走偏了。

修复后的代码： #

def inorderTraversal(currentNode, output=None):
    if output is None:
        output = []
    # 先递归遍历左子树，不需要return，继续往下执行
    if currentNode.left:
        inorderTraversal(currentNode.left, output)
    # 将当前节点的值加入列表，append是修改原列表，不需要返回它的结果
    output.append(currentNode.data)
    # 最后递归遍历右子树
    if currentNode.right:
        inorderTraversal(currentNode.right, output)
    # 所有遍历完成后，返回最终的结果列表
    return output

为什么这样能解决问题？ #

1. 去掉了左子树遍历后的return，保证左子树遍历完后，会继续处理当前节点，再遍历右子树，完全符合中序遍历的顺序。
2. 不再返回append()的结果，而是最后统一返回整个output列表——因为列表是可变对象，递归过程中所有修改都会作用在同一个列表上。
3. 当你的输入树是「根节点1，左孩子3，右孩子2」时，执行这个函数就会得到预期的[3,1,2]。

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