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.
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++
kotlin這次不是要求數量,而是真的要建 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++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} | |
}; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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 | |
} | |
} |
沒有留言:
張貼留言