Python recursive / DP solution,


#1

class Solution:
def generateTrees(self, A,*args):
import itertools as its
if len(args)==0 :
a,dic=1,{}
#we use a dictionnary to store answers for a,A:
#The list of all structurally unique BST’s (binary search trees) that store values a…A.
else :
a,dic=args

    if (a,A) in dic :
        return dic[(a,A)]
    elif a>A :
        return [None]
    elif A ==a :
        dic[(a,A)]=[TreeNode(a)]
        return dic[(a,A)]
    else :     
        dic[(a,A)] = []
        for i in range(a,A+1) : # loop over the root node
            leftList=self.generateTrees(i-1,a,dic)
            rightList=self.generateTrees(A,i+1,dic)
            for left,right in its.product(leftList,rightList) : 
            #  loop over all possibilities of left tree arrangement and right tree arrangement
                tn=TreeNode(i)
                tn.left=left
                tn.right=right
                dic[(a,A)] += [tn]
        return dic[(a,A)]

#2

I dont understand how you used DP. Isnt every tree & its subtree unique. So, whose value are you storing & which work is been computed more than once.


#3

The problem asks you the possibilities when nodes’ values are from 1 to A : 1, 2, 3,…,A-2, A-1, A
I generalize a bit and solve when values are from a to A : a, a+1,a +2,…, A-2, A-1, A
I store the answer for the tuple (a,A) in a dictonnary : dic
and compute by recursion : a tree for the tuple (a,A) will have a root value : i, I loop through the possibilities of i : a to A, and for that tree the left subtree will be amongst the trees for tuple (a,i-1) and right one : (i+1,A)

Another way of seeing it is that I treat the list of possibilities according to the value of the root node. so for tuple (2,5) sor example, the root node has value 2,3,4, or 5 so I list the posibilities for 2 then 3 … then 5. when listing possibilities for root node = 4 : left subtree will have node 2 to 3, right one : 5 to 5.
so my possibilities of trees with root node 4 are any left tree 2-3 and anyright tree 5-5, with 4 as root. (so we have to iterate through the “product” of the possible left and right trees

The DP is there to store intermediate recursive call as there will be several : the 2-5 call can happen for right subtrees in call 1-5 with i=1, or left subtrees in call 2-x, with i =6 (x>=6)

I hope that’s clear enough. It is hard to explain without drawing…