# Unique Binary Search Trees II

## Question

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

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


## 题解

Unique Binary Search Trees 的升级版，这道题要求的不是二叉搜索树的数目，而是要构建这样的树。分析方法仍然是可以借鉴的，核心思想为利用『二叉搜索树』的定义，如果以 i 为根节点，那么其左子树由[1, i - 1]构成，右子树由[i + 1, n] 构成。要构建包含1到n的二叉搜索树，只需遍历1到n中的数作为根节点，以i为界将数列分为左右两部分，小于i的数作为左子树，大于i的数作为右子树，使用两重循环将左右子树所有可能的组合链接到以i为根节点的节点上。

helper(start, end) {
result;
if (start > end) {
result.push_back(NULL);
return;
} else if (start == end) {
result.push_back(TreeNode(i));
return;
}

// dfs
for (int i = start; i <= end; ++i) {
leftTree = helper(start, i - 1);
rightTree = helper(i + 1, end);
// link left and right sub tree to the root i
for (j in leftTree ){
for (k in rightTree) {
root = TreeNode(i);
root->left = leftTree[j];
root->right = rightTree[k];
result.push_back(root);
}
}
}

return result;
}


1. helper(1,3)
• [leftTree]: helper(1, 0) ==> return NULL
• ---loop i = 2---
• [rightTree]: helper(2, 3)
1. [leftTree]: helper(2,1) ==> return NULL
2. [rightTree]: helper(3,3) ==> return node(3)
3. [for loop]: ==> return (2->3)
• ---loop i = 3---
1. [leftTree]: helper(2,2) ==> return node(2)
2. [rightTree]: helper(4,3) ==> return NULL
3. [for loop]: ==> return (3->2)
2. ...

### Python

"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
# @paramn n: An integer
# @return: A list of root
def generateTrees(self, n):
return self.helper(1, n)

def helper(self, start, end):
result = []
if start > end:
result.append(None)
return result

for i in xrange(start, end + 1):
# generate left and right sub tree
leftTree = self.helper(start, i - 1)
rightTree = self.helper(i + 1, end)
# link left and right sub tree to root(i)
for j in xrange(len(leftTree)):
for k in xrange(len(rightTree)):
root = TreeNode(i)
root.left = leftTree[j]
root.right = rightTree[k]
result.append(root)

return result


### C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @paramn n: An integer
* @return: A list of root
*/
vector<TreeNode *> generateTrees(int n) {
return helper(1, n);
}

private:
vector<TreeNode *> helper(int start, int end) {
vector<TreeNode *> result;
if (start > end) {
result.push_back(NULL);
return result;
}

for (int i = start; i <= end; ++i) {
// generate left and right sub tree
vector<TreeNode *> leftTree = helper(start, i - 1);
vector<TreeNode *> rightTree = helper(i + 1, end);
// link left and right sub tree to root(i)
for (int j = 0; j < leftTree.size(); ++j) {
for (int k = 0; k < rightTree.size(); ++k) {
TreeNode *root = new TreeNode(i);
root->left = leftTree[j];
root->right = rightTree[k];
result.push_back(root);
}
}
}

return result;
}
};


### Java

/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/
public class Solution {
/**
* @paramn n: An integer
* @return: A list of root
*/
public List<TreeNode> generateTrees(int n) {
return helper(1, n);
}

private List<TreeNode> helper(int start, int end) {
List<TreeNode> result = new ArrayList<TreeNode>();
if (start > end) {
return result;
}

for (int i = start; i <= end; i++) {
// generate left and right sub tree
List<TreeNode> leftTree = helper(start, i - 1);
List<TreeNode> rightTree = helper(i + 1, end);
// link left and right sub tree to root(i)
for (TreeNode lnode: leftTree) {
for (TreeNode rnode: rightTree) {
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
}
}
}

return result;
}
}


### 源码分析

1. 异常处理，返回None/NULL/null.
2. 遍历start->end, 递归得到左子树和右子树。
3. 两重for循环将左右子树的所有可能组合添加至最终返回结果。