[Leetcode] DP-- 95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
           /     /      /       
     3     2     1      1   3      2
    /     /                        
   2     1         2                 3

Solution:

this is a little difficult than the "96 Unique Binary Search Trees I"
it requires to get all the unique binary search tree stored.

1. 1st try to use iterative way

define dpT[i] indicate the treenodes stored in last all rooted as i

dpT[i]

dpT[0] = []

dpT[1] = [TreeNode(1)]

dp[2] = dp[0]*dp[1] + dp[1]*dp[0]

for e in dpT[1]

t2 = TreeNode(2)

t2.right = e

dpT[2].append(t2)

for e in dpT[1]

t1 = TreeNode(1)

t1.left = e

dpT[2].append(t1)

dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]

if i == 0:

for e in dpT[2] //k-i-1

root = TreeNode(1) // 1

root.right = e

dpT[3].append(root） //k

else if i == 2: //k-1

for e in dpT[2] //i

root = TreeNode(3) // k

root.left = e

dpT[3].append(root) //k

else:

for e1 in dpT[1]: //i

for e2 in dpT[1]: //k-i-1

root = TreeNode(2] // i e.g. 2 is the second element important

root.left = e1

root.right = e2

dpT[3].append(root) //k

2. use recursive way

leftsubtree (1, k-1)

root (k)

rightsubtree(k+1, n)

 1  def generateTreeHelper(left, right):
 2             lst = []
 3             if left > right:
 4                 lst.append(None)
 5                 return lst
 6             
 7             for i in range(left, right+1, 1):
 8                 lSubTree = generateTreeHelper(left, i-1)
 9                 rSubTree = generateTreeHelper(i+1, right)
10                 for j in range(0, len(lSubTree)):
11                     for k in range(0, len(rSubTree)):
12                         root = TreeNode(i)
13                         root.left = lSubTree[j]
14                         root.right = rSubTree[k]
15                         lst.append(root)
16             return lst
17         if n == 0:
18             return []
19         return generateTreeHelper(1, n)