Accepted recursive solution in python


  • 2
    L

    The code looks chunky. Any suggestion would be appreciated!

     class Solution:
        # @return a list of tree node
        def generateTrees(self, n):
            # global variable to record possible trees for i (i<n)
            dict={0:[None],1:[TreeNode(1)]}
            # recurssively copy the tree.
            def TreeCopy(root,n):
                if not root:
                    return None
                root1,root1.left,root1.right=TreeNode(root.val+n),TreeCopy(root.left,n),TreeCopy(root.right,n)
                return root1
            def GenerateBST(n):
                if dict.has_key(n):
                    return dict[n]
                list=[]
                # given the tree node ii, the combination of left child tree(1:ii-1) and right tree(ii+1:n) make all the possible trees.
                for ii in range(1,n+1):
                    listLeft,listRight=GenerateBST(ii-1),GenerateBST(n-ii)
                    for treeLeft in listLeft:
                        for treeRight in listRight:
                            tmp,tmp.left,tmp.right=TreeNode(ii),TreeCopy(treeLeft,0),TreeCopy(treeRight,ii)
                            list.append(tmp)
                dict[n]=list
                return list
            return GenerateBST(n)

  • 0
    Q

    function generateTrees return a list of trees according to input n, and
    function TreeCopy copy and return a new node where each child and the root itself is added by input n

    in GenerateBST:
    ii is the root value, it ranges from 1 to n
    then it uses two for loops to get all possible left and right sub-trees.
    for left sub-tree, simply copy it without adding any value
    for right sub-tree, the structure is correct but you need to add certain value to each of the node, according to the root value

    Awesome, how neat this code is !!!.


Log in to reply
 

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