Why do we need a deepcopy here?


  • 0
    S

    This is a brilliant python solution, but I am a little confused about the use of deepcopy here...Hope someone can give me a hand. Thx in advance!


  • 1
    G

    Here is a little experiment I just did on deepcopy on python 2.7.8:

    This editor is really a pain. I will just insert a screenshot.

    deepcopy

    Notice that it deepcopied all its attributes.

    The answer from your link:

    class Solution:
    def build(self, nodes):
        n = len(nodes)
        if n == 0:
            yield None
            return
        for i in range(n):
            root = nodes[i]
            for left in self.build(nodes[:i]):
                for right in self.build(nodes[i+1:]):
                    root.left, root.right = left, right
                    yield root
    
    # @return a list of tree node
    def generateTrees(self, n):
        nodes = map(TreeNode, range(1, n + 1))
        return map(copy.deepcopy, self.build(nodes))
    

    Assume you know clearly what generators does in python. To be short, they throw out values without returning. The build function just changes links among nodes, while nodes are generated at the first line of generateTrees function in advance. So in the last line of code, the map function, it iterate through all possible root nodes with different links. If he does not deepcopy here, the links will be changed in next iteration, the tree will be messed up.

    When I first did this question, I totally did not realize one can use generator and deepcopy in this way. My code failed because of interface mismatch among functions after all. I went to discuss of the problem, and then saw your question. This is the best solution I have ever seen in python on leetcode till now.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.