Brief python DP solution


  • 0
    C

    Idea is simple. Like in the version 1 question, you start from N=1 up to the desired number. for each N, you construct the list of trees, dynamically. Each N uses the trees of the smaller Ns as the left and right trees, that's effortless, well, almost.

    For left trees, you can always reuse the exact same object that you have constructed for the smaller Ns, since they will always be the same. For the right trees, you will need to substitute the values in the pre-existing trees with the values you have on the right, since the structure of the trees are the same. And since you need to change the values for the right trees, you do this by constructing a new tree, otherwise you would change the copy that is shared by many trees.

    class Solution:
        # @return a list of tree node
    
        def treeNumSubstitution(self, root,numList):
            if root is None:
                return None
            newRoot=TreeNode(numList[root.val-1])
            if root.left:
                newRoot.left=self.treeNumSubstitution(root.left,numList)
            if root.right:
                newRoot.right=self.treeNumSubstitution(root.right,numList)
            return newRoot
    
        def generateTrees(self, n):
            num2Trees=dict()
            num2Trees[0]=[None]
            for i in xrange(1,n+1):
                num2Trees[i]=[]
                for rootPos in xrange(1,i+1):
                    for leftTree in num2Trees[rootPos-1]:
                        for rightTree in num2Trees[i-rootPos]:
                            root=TreeNode(rootPos)
                            num2Trees[i].append(root)
                            rightTree=self.treeNumSubstitution(rightTree,range(rootPos+1,i+1))
                            root.left=leftTree
                            root.right=rightTree
            return num2Trees[n]

Log in to reply
 

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