# Accepted recursive solution in python

• 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)]}
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)``````

• 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 !!!.

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