• Time:O(3^n)
• Space:O(3^n)

## C++

``````class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0)
return {};
return generateTrees(1, n);
}

private:
vector<TreeNode*> generateTrees(int min, int max) {
if (min > max)
return {nullptr};

vector<TreeNode*> ans;

for (int i = min; i <= max; ++i)
for (TreeNode* left : generateTrees(min, i - 1))
for (TreeNode* right : generateTrees(i + 1, max)) {
ans.push_back(new TreeNode(i));
ans.back()->left = left;
ans.back()->right = right;
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0)
return new ArrayList<>();
return generateTrees(1, n);
}

private List<TreeNode> generateTrees(int min, int max) {
if (min > max)
return Arrays.asList((TreeNode) null);

List<TreeNode> ans = new ArrayList<>();

for (int i = min; i <= max; ++i)
for (TreeNode left : generateTrees(min, i - 1))
for (TreeNode right : generateTrees(i + 1, max)) {
ans.get(ans.size() - 1).left = left;
ans.get(ans.size() - 1).right = right;
}

return ans;
}
}
``````

## Python

``````class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []

def generateTrees(mini: int, maxi: int) -> List[Optional[int]]:
if mini > maxi:
return [None]

ans = []

for i in range(mini, maxi + 1):
for left in generateTrees(mini, i - 1):
for right in generateTrees(i + 1, maxi):
ans.append(TreeNode(i))
ans[-1].left = left
ans[-1].right = right

return ans

return generateTrees(1, n)
``````