二叉树前序遍历两种递归实现输出结果不一致原因排查

前序遍历是基础的二叉树递归遍历操作，两种写法逻辑看似一致，运行表现却存在明显差异。

测试信息 #

• 统一测试输入：

[1,null,2,3]
[]
[1]

• 对应预期输出：

[1,2,3]
[]
[1]

两种实现对比 #

第一种实现（运行结果错误） #

代码：

class Solution:
    ans=[]
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return
        self.ans.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)
        
        return self.ans

实际运行输出：

[1,2,3]
[]
[1,2,3,1]

第二种实现（运行结果正确） #

代码：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        self.ans=[]
        def preorder(root):
            if root is None:
                return
            self.ans.append(root.val)
            preorder(root.left)
            preorder(root.right)
        preorder(root)
        return self.ans

该实现可以全部通过测试用例，返回符合预期的结果。

第一种实现的错误原因 #

第一种写法存在两个核心问题：

1. 变量作用域错误：把存储结果的ans定义为类属性，这个属性是所有Solution类实例共享的，不会在每次调用preorderTraversal方法时自动重置。在线判题系统一般会复用同一个类实例执行所有测试用例，跑完第一个用例后ans里已经存了[1,2,3]，执行第三个用例[1]时，直接在原有残留数据的基础上追加1，就得到了错误的[1,2,3,1]。
2. 边界分支返回值错误：当传入的根节点为空时，会触发if root is None: return分支，这个分支没有返回任何值，实际会返回None，和题目要求返回空列表的规则不符。

第二种写法每次进入preorderTraversal方法时，都会先执行self.ans=[]，把结果列表重置为空，相当于每次调用都使用全新的列表存储结果，不存在历史数据残留的问题，因此能得到正确结果。

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