Python递归与全局变量问题：N叉树前序遍历单方法实现异常

你遇到的问题根源在于全局变量test的复用：LeetCode在执行多组测试用例时，全局变量不会被重新初始化，每次调用preorder都会往同一个数组中追加元素，导致后续测试用例的结果叠加到前一个的结果里。

方案1：利用递归返回值拼接 #

这种方式不需要额外辅助函数，直接在单个方法里通过递归返回的子节点遍历结果拼接出当前节点的前序遍历数组：

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if not root:
            return []
        # 先记录当前节点值，再依次拼接所有子节点的前序遍历结果
        result = [root.val]
        for child in root.children:
            result.extend(self.preorder(child))
        return result

方案2：方法内嵌套递归函数 #

如果更习惯原有的"追加"逻辑，可以在preorder内部定义嵌套的递归函数，用局部数组存储结果，避免全局变量的问题：

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        def traverse(node):
            if not node:
                return
            # 往局部数组中追加当前节点值
            result.append(node.val)
            for child in node.children:
                traverse(child)
        
        result = []
        traverse(root)
        return result

为什么这两种方案能解决问题？ #

• 两种方案都使用局部变量存储遍历结果，每次调用preorder时都会重新创建新的数组，不同测试用例的数组完全独立，不会出现内容累加的情况。
• 方案1通过递归返回子节点的遍历结果，直接拼接成当前节点的结果；方案2用嵌套函数操作局部数组，逻辑和你最初的双方法实现一致，但把辅助函数放到了preorder内部，保持单方法的结构。

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