2016年12月11日 星期日

[LeetCode] 95. Unique Binary Search Trees II

轉自LeetCode

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>

這題是 Unique Binary Search Tree 的衍生題

這題的觀念也可以用在 241. Different Ways to Add Parentheses

這次不是要求數量,而是真的要建 BST 出來

首先,將 n = 3 所產生的 BST 重新整理一下

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

可以看出,以 i 為 root 的 BST, i 在 [1,n] 之間

左子樹等同於 1 到 i-1 形成的子樹( 當 1 > i-1 時,為 NULL)

右子樹等同於 i+1 到 n 形成的子樹( 當 i+1 > n 時,為 NULL)

可以用這個性質,搭配 DFS 來建 BST (參考資料)

這邊的 DFS 使用的是 pointer of vector<TreeNode *>,這是要用來節省空間的使用(參考資料)

code 如下
c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if(n == 0){
return vector<TreeNode *>();
}
//> use DFS to generate tree
return *generateTreesDFS(1, n);
}
//> for BST uses value i as root, i is one of the positive number of 1、2、..、n
//> the left subtree is formed by number 1 to i-1
//> the right subtree is formed by number i+1 to n
vector<TreeNode *> *generateTreesDFS(const int &start, const int &end) {
vector<TreeNode *> *subTree = new vector<TreeNode *>();
if(start > end) {
subTree->push_back(NULL);
}
else {
for(int i = start; i <= end; i++) {
vector<TreeNode *> *leftSubTree = generateTreesDFS(start, i-1);
vector<TreeNode *> *rightSubTree = generateTreesDFS(i+1, end);
//> combine
for(int left = 0; left < leftSubTree->size(); left++) {
for(int right = 0; right < rightSubTree->size(); right++) {
TreeNode *node = new TreeNode(i);
node->left = (*leftSubTree)[left];
node->right = (*rightSubTree)[right];
subTree->push_back(node);
}
}
}
}
return subTree;
}
};
kotlin
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun generateTrees(n: Int): List<TreeNode?> {
return dfs(1, n)
}
fun dfs(start: Int, end: Int): List<TreeNode?> {
val result = mutableListOf<TreeNode?>()
if(start > end) {
result.add(null)
} else {
for(i in start..end) {
val left = dfs(start, i-1)
val right = dfs(i+1, end)
for(j in left.indices) {
for(k in right.indices) {
val node = TreeNode(i)
node.left = left[j]
node.right = right[k]
result.add(node)
}
}
}
}
return result
}
}

沒有留言:

張貼留言