###### tags: `Leetcode` `medium` `dynamic programming` `tree` `python`

# 95. Unique Binary Search Trees II

## [題目連結:] https://leetcode.com/problems/unique-binary-search-trees-ii/

## 題目:
Given an integer ```n```, return all the structurally unique **BST**'s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in **any order**.


#### [圖片來源:] https://leetcode.com/problems/unique-binary-search-trees-ii/

## 解題想法:
兄弟題目: [96. Unique Binary Search Trees](/0tFv4d9vSM-WIC_uKucQ5A)

* [96. Unique Binary Search Trees](/0tFv4d9vSM-WIC_uKucQ5A) 為求n個node能組成之BST之個數，而此題為要求，輸出實際tree構造

* dfs:
* 傳遞參數: (start,end)
* 表示由start到end的node構成的BST
* ex: (1,n) : 由1~n構成
* ex: (2,4) : 由node 2,3,4構成
* 終止條件:
* 若start>end:
* return [None]
* 每次選i為root:
* 遞迴求左子樹: Left_Tree
* 可由start~(i-1)的node構成
* 遞迴求右子樹: Right_Tree
* 可由(i+1)~end的node構成
* ex: start=1 end=7
* i=4
* 左子樹=dfs(1,3) -> 由1,2,3構成
* 右子樹=dfs(5,7) -> 由5,6,7構成
* 連結:
* 因為遞迴求的左右子樹，分別回傳list，該list中存的元素為root，每個root都有其其獨特的結構
* 因此連結方式為

for l_root in Left_Tree:
    for r_root in Right_Tree:
        root = TreeNode(i)
        root.left =l_root
        root.right=r_root
        res.append(root)

## Python: (dfs)

#https://www.twblogs.net/a/5cba808fbd9eee0f00a2573e
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left = TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root = self
        que = [root]
        res=[]
        while que:
            root=que.pop(0)
            res.append(root.val)
            if root.left:
                que.append(root.left)
            if root.right:
                que.append(root.right)
        print(res)

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        return self.dfs(1,n)
    #由start到end的node構成的BST
    def dfs(self,start,end):
        res = []
        if start>end:
            return [None]
        #選i為root
        for i in range(start,end+1):
            #以i為root
            #左子數: 可由start~i-1的node構成
            #右子數: 可由i+1~end的node構成
            Left_Tree = self.dfs(start,i-1)
            Right_Tree = self.dfs(i+1,end)
            #連結root
            for l_root in Left_Tree:
                for r_root in Right_Tree:
                    root = TreeNode(i)
                    root.left =l_root
                    root.right=r_root
                    res.append(root)
        return res
            
result = Solution()
ans = result.generateTrees(3)
for i in range(len(ans)):
    ans[i].printTree()
    
'''
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[3, 1, 2]
[3, 2, 1]
'''

## Python: (dp+dfs)
* 優化:
* 使用字典path紀錄已使用過的pair(start,end)
* 若該pair已在path 直接回傳使用即可

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        self.path={}
        return self.dfs(1,n)
    def dfs(self,start,end):
        if start>end:
            return [None]
        if start==end: #自己一點構成樹
            return [TreeNode(start)]
        #若該pair已在path 直接回傳使用即可
        if (start,end) in self.path:
            return self.path[(start,end)]
        res=[]
        #由start~end的node構成BST
        for i in range(start,end+1):
            Left_Tree=self.dfs(start,i-1)
            Right_Tree=self.dfs(i+1,end)
            for rootL in Left_Tree:
                for rootR in Right_Tree:
                    root=TreeNode(i)
                    root.left=rootL
                    root.right=rootR
                    res.append(root)
        #存入此start~end所構成的BST的所有組合結構
        self.path[(start,end)]=res
        return res