Leetcode --- Unique Binary Search Trees II(Medium)
===

## Description

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.

**給n表示所有數字1~n,將所有用這些數字所組成的不同構的BST列出來.**

### Example

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

**Input**: n = 3
**Output**: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

### Constraint
* 1 <= n <= 8

## Solutions

* **Method 1: Recursion**

所有不同的組合的解 => root =1,2,...,n都要排列過,所以拆成
Sol(n) = sol(root=1) +sol(root=2) +... + sol(root=n)
再帶入BST特性:若root = i => 左子會有**1~ i-1**的數字做組合,右子會有**i+1~n**的數字做組合,再遞迴.

### Implement code

class Solution {
    public List<TreeNode> generateTrees(int n) {
       return helper(1,n);
    }
    private List<TreeNode> helper(int st,int ed)
    {
        List<TreeNode> res =new ArrayList<>();
        if(st>ed)
        {
            res.add(null);
            return res;
        }
        for(int i =st ; i<=ed ;i++)
        {
            List<TreeNode> left = helper(st,i-1);
            List<TreeNode> right = helper(i+1,ed);
            for(TreeNode l : left)
                for(TreeNode r : right)
                {
                    TreeNode ans = new TreeNode(i,l,r);
                    res.add(ans);
                }
        }
         return res;
    }
}

line 8: 停止條件:當要排列的數字大於root則填null
line 17,18:將所有得到的左右子做組合

### Submission on Leetcode

Runtime: **1 ms, faster than 93.80%** of Java online submissions for Unique Binary Search Trees II.
Memory Usage: **39.6 MB, less than 61.99%** of Java online submissions for Unique Binary Search Trees II.

---

* **Method 2: DP**
觀察n=2,n=3

n=2
 
1         2   
 \       /
  2     1

n=3

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

新插入的數字一定大於前一個case,==**所以只會出現在root** , **root.rightChild** , **root.rightChild.rightChild** , **....**==
所以變成

==若插入位置原本有node則此串node變成新node的左子==

=>

Org:
        1
         \
          2
           \
            3
Insert(4)在pos 1

        1
         \
          4
         /
       2
        \
         3

### Implement code

class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> ans = new ArrayList<>();
        if(n==0)
        {
            ans.add(null);
            return ans;
        }
        
        List<TreeNode> preL = generateTrees(n-1);
        
        for(TreeNode pre : preL)
        {
            for(int i =0;i<n;i++)
            {
                TreeNode res = insertcur(pre,i,n);
                if(res != null)
                    ans.add(res);
            }
        }
        return ans;
    }
    private TreeNode detect(TreeNode preT ,int pos)
    {  
        int i =0;
        while(i<pos-1)
        {
            if(preT ==null)
            {
                break;
            }
            preT =preT.right ;
            i++;
        }
        return preT;
    }
    private TreeNode insertcur(TreeNode pre,int pos,int cur)
    {
        TreeNode preT = copyT(pre);
        TreeNode head =preT;
        TreeNode curT = new TreeNode(cur);
        if(pos ==0)
        {
            curT.left =preT;
            return curT;
        }
        TreeNode part = detect(preT,pos);
        if(part ==null)
        {
            return null;
        }
            
        if(part.right == null)
        {
            part.right = curT;
        }
        else
        {
            curT.left = part.right;
            part.right =curT;
        }
        return head;
       
    }
    private TreeNode copyT(TreeNode T)
    {
        if(T ==null)
            return null;
        TreeNode newT = new TreeNode();
        newT.val =T.val;
        newT.left = copyT(T.left);
        newT.right = copyT(T.right);
        return newT;
    }
}

* function:detect(TreeNode preT ,int pos)
探測第pos位置的右子是否為null,root 為 position 0,若尚未探到目標pos則已為null則此case須被丟棄,直接回傳null.
為了之後好操作少探測一次,之後可以用preT.right來增減樹

* function:insertcur(TreeNode pre,int pos,int cur)
在n-1的解pre中,對第pos位置的右子插入Node(cur)
必須用copyTree來保護,因為一個pre會被操作很多次,把pos=0作為特別解,額外處理,其他部分做detect來看要不要做修正,detect=null時為被丟棄的case

* Main
對每一個上一個解,把新node分別嘗試插在root,root.right .....

### Submission on Leetcode

Runtime: **1 ms, faster than 93.76%** of Java online submissions for Unique Binary Search Trees II.
Memory Usage: **39.8 MB, less than 31.59%** of Java online submissions for Unique Binary Search Trees II.

###### tags: `Leetcode` `Medium` `DP` `Tree`