aboutsummaryrefslogtreecommitdiff
path: root/unique_bst2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'unique_bst2.cpp')
-rw-r--r--unique_bst2.cpp34
1 files changed, 34 insertions, 0 deletions
diff --git a/unique_bst2.cpp b/unique_bst2.cpp
new file mode 100644
index 0000000..438d9b7
--- /dev/null
+++ b/unique_bst2.cpp
@@ -0,0 +1,34 @@
+// 95. Unique Binary Search Trees II
+#include "leetcode.h"
+
+/*
+ * given an integer 'n', return all the structurally unique BST's which has
+ * exactly 'n' nodes of unique values from 1 to 'n'. return the answer in any
+ * order.
+ */
+
+class Solution {
+ vector<TreeNode *> build(int from, int to) {
+ vector<TreeNode *> res;
+ if (to - from < 0)
+ res.push_back(0);
+ if (to - from == 0)
+ res.push_back(new TreeNode(from));
+ if (to - from > 0)
+ for (int i = 0; i <= to; i++) {
+ vector<TreeNode *> left = build(from, i - 1);
+ vector<TreeNode *> right = build(i + 1, to);
+ for (int j = 0; j < left.size(); j++)
+ for (int k = 0; k < right.size(); k++) {
+ TreeNode *height = new TreeNode(i);
+ height->left = left[j];
+ height->right = right[k];
+ res.push_back(height);
+ }
+ }
+ return res;
+ }
+
+public:
+ vector<TreeNode *> generateTrees(int n) { return build(1, n); }
+};