LeetCode algorithm #257 Binary Tree Paths

March 1, 2022

For the LeetCode algorithm problem #257 Binary Tree Paths. I know we can use empty string path to concate node values, but why do I also always get output like [[1,2,5,3],[1,2,5,3]] when i try to use list path to store node value?

code:

class Solution:
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        # dfs
        
        res = []
        def helper(node, path):
            
            if not node: return 
            
            #path+=str(node.val)
            path.append(node.val)

            # leaf node
            if not node.left and not node.right:
                res.append(path)
                #return

            #path += '->'  
            helper(node.left, path)
            helper(node.right, path)

        helper(root, [])
        return res

test case : [1,2,3,null,5]

>Solution :

You’re passing through a reference to the same path list to both recursive calls, so appending in those calls (and each recursive call) will append to the same list.

Strings are immutable. Mutating a string returns a new reference, thus why the solution may work using strings instead.