95. Unique Binary Search Trees II
給定一個整數 n，返回所有具有 n 個節點且節點值唯一的結構上唯一的二叉搜索樹（BST）。這些節點值為 1 到 n。以任意順序返回答案。
範例 1：
輸入：n = 3 輸出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
if n == 0:
return []
def generate(start, end):
if start > end:
return [None]
all_trees = []
for i in range(start, end + 1):
# Generate all possible left subtrees
left_trees = generate(start, i - 1)
# Generate all possible right subtrees
right_trees = generate(i + 1, end)
# Combine left and right subtrees with the current root
for l in left_trees:
for r in right_trees:
current_tree = TreeNode(i)
current_tree.left = l
current_tree.right = r
all_trees.append(current_tree)
return all_trees
return generate(1, n)
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0) return vector<TreeNode*>();
return generateTreesHelper(1, n);
}
private:
vector<TreeNode*> generateTreesHelper(int start, int end) {
vector<TreeNode*> allTrees;
if (start > end) {
allTrees.push_back(nullptr);
return allTrees;
}
for (int i = start; i <= end; i++) {
vector<TreeNode*> leftSubtrees = generateTreesHelper(start, i - 1);
vector<TreeNode*> rightSubtrees = generateTreesHelper(i + 1, end);
for (TreeNode* left : leftSubtrees) {
for (TreeNode* right : rightSubtrees) {
TreeNode* root = new TreeNode(i);
root->left = left;
root->right = right;
allTrees.push_back(root);
}
}
}
return allTrees;
}
};
19.07MB, 13ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number} n
* @return {TreeNode[]}
*/
var generateTrees = function(n) {
};
19.07MB, 13ms
