# 74：Unique Binary Search Trees II

xiaoxiao2021-03-26  10

题目：Given 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. 题目具体形式见 https://leetcode.com/problems/unique-binary-search-trees-ii/?tab=Description

下面解法代码的思想及编写参考了网址https://github.com/soulmachine/leetcode#leetcode题解题目，用的是递归方法 ，代码如下：

class Solution { public: vector<TreeNode*> generateTrees(int n) { if (n == 0) return vector<TreeNode*>(); return generate(1, n); } private: vector<TreeNode*> generate(int start, int end) { vector<TreeNode*> subTree; if (start > end) { subTree.push_back(nullptr); return subTree; } for (int k = start, k <= end; ++k) { vector<TreeNode*> leftSubs = generate(start, k - 1); vector<TreeNode*> rightSubs = generate(k + 1, end); for (auto i : leftSubs) for (auto j : rightSubs) { TreeNode* node = new TreeNode(k); node -> left = i; node -> right = j; subTree.push_back(node); } } return subTree; } };