Inorder Binary Tree Traversal问题：递归实现中列表无法正确追加元素
2026-7-1
问题原因
你代码的核心问题是每次递归调用inoder函数时，都会创建一个全新的空visited列表。递归处理左子树、右子树时，它们各自生成的遍历结果没有被合并到当前层的列表中，只有当前节点的值被添加到了自己的visited里。最终返回的是最上层调用（处理根节点1）的visited，里面自然只有根节点的值。
而控制台能正确打印所有值，是因为每个递归分支里的print(bomj.val)都会按中序遍历的顺序执行，和列表的独立存储无关。
修正方案
这里提供两种可行的修正方式：
方式1：将列表作为参数传递（共用同一个列表）
把visited设为可选参数，递归时传递同一个列表，避免重复创建：
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def inoder(bomj, visited=None): # 初始化空列表，仅在第一次调用时执行 if visited is None: visited = [] if bomj: inoder(bomj.left, visited) visited.append(bomj.val) inoder(bomj.right, visited) return visited tree = TreeNode(1) tree.left = TreeNode(2) tree.right = TreeNode(3) tree.left.left = TreeNode(4) tree.left.right = TreeNode(5) tree.left.left.left = TreeNode(7) tree.right.left = TreeNode(6) print(inoder(tree)) # 输出: [7, 4, 2, 5, 1, 6, 3]
方式2：合并递归返回的结果
直接将左子树、右子树的递归遍历结果合并到当前列表中：
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def inoder(bomj): visited = [] if bomj: # 合并左子树的遍历结果 visited += inoder(bomj.left) visited.append(bomj.val) # 合并右子树的遍历结果 visited += inoder(bomj.right) return visited tree = TreeNode(1) tree.left = TreeNode(2) tree.right = TreeNode(3) tree.left.left = TreeNode(4) tree.left.right = TreeNode(5) tree.left.left.left = TreeNode(7) tree.right.left = TreeNode(6) print(inoder(tree)) # 输出: [7, 4, 2, 5, 1, 6, 3]
内容的提问来源于stack exchange，提问作者Nei
相关产品推荐
相关产品推荐
