Recursion in python and global variables-CodePudding

I'm doing the n-ary tree preorder traversal on leetcode.

I have this solution that uses two methods:


"""
# 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):
       
       output = []

       self.recur(root, output)

       return output

   def recur(self, root, output):

       if not root:
           return []
       
       output.append(root.val)
       for x in root.children:
           self.recur(x, output)

I was wondering how to do the same recursion using one method. The solution below gives me problems. Namely, when leetcode is running testcases, it aggregates the output. I.e. the output array for test case #2 is appended to test case #1's out put array.

So: Testcase 1 output = [Test 1 solution] Testcase 2 output = [Test 1 solution, Test Case 2 solution]


test = []
class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """

        if not root:
            return []

        test.append(root.val)
        for x in root.children:
            self.preorder(x)

        return test

CodePudding user response：

You should likely not be using global variables as part of this leetcode challenge, as leetcode is likely creating a new class instance of Solution for each test case. The easiest way to resolve this would be to create a class constructor that initializes your list. This will remove the global variable which is causing the issues you've mentioned.

class Solution(object):
    def __init__(self):
        self.test = []

    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """

        if not root:
            return self.test

        self.test.append(root.val)
        for x in root.children:
            self.preorder(x)

        return self.test

CodePudding user response：

Rather than moving the output list to be a global or instance variable, you can make it an argument with a default value, so that you can directly call the recursive version of your function. You won't want to directly initialize to an empty list though, as default arguments for functions and methods are created only once, at function compile time. The same object is then reused for every call that doesn't include a value for that argument. For a mutable object like a list, that's no good (indeed, it's basically another version of your global list).

Instead, use a sentinel value, like None to indicate when nothing has been passed, and check for it in the body of the method:

class Solution(object):
    def preorder(self, root: Node, output: Optional[list]=None) -> list:
        if output is None:
            output = []

        if root is not None:
            output.append(root.val)
            for x in root.children:
                self.preorder(x, output)

        return output