本文主要是介绍LeetCode 题解（156）: Unique Binary Search Trees II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
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.
1 3 3 2 1\ / / / \ \3 2 1 1 3 2/ / \ \2 1 2 3
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
题解：
用每一个数做根，递归左右。
C++版：
class Solution {
public:vector<TreeNode*> generateTrees(int n) {return generateTree(1, n);}vector<TreeNode*> generateTree(int left, int right) {vector<TreeNode*> result;if(left > right) {result.push_back(NULL);return result;}for(int i = left; i <= right; i++) {vector<TreeNode*> leftRes = generateTree(left, i - 1);vector<TreeNode*> rightRes = generateTree(i + 1, right);for(int j = 0; j < leftRes.size(); j++) {for(int k = 0; k < rightRes.size(); k++) {TreeNode* root = new TreeNode(i);root->left = leftRes[j];root->right = rightRes[k];result.push_back(root);}}}return result;}
};Java版：
public class Solution {public List<TreeNode> generateTrees(int n) {return generateTree(1, n);}public List<TreeNode> generateTree(int left, int right) {List<TreeNode> result = new ArrayList<TreeNode>();if(left > right) {result.add(null);return result;}for(int i = left; i <= right; i++) {List<TreeNode> leftRes = generateTree(left, i - 1);List<TreeNode> rightRes = generateTree(i + 1, right);for(int j = 0; j < leftRes.size(); j++) {for(int k = 0 ; k < rightRes.size(); k++) {TreeNode root = new TreeNode(i);root.left = leftRes.get(j);root.right = rightRes.get(k);result.add(root);}}}return result;}
}Python版：
class Solution:# @param {integer} n# @return {TreeNode[]}def generateTrees(self, n):return self.generateTree(1, n)def generateTree(self, left, right):if left > right:return [None]result = []for i in range(left, right+1):leftRes = self.generateTree(left, i - 1)rightRes = self.generateTree(i + 1, right)for j in range(len(leftRes)):for k in range(len(rightRes)):root = TreeNode(i)root.left = leftRes[j]root.right = rightRes[k]result.append(root)return result这篇关于LeetCode 题解（156）: Unique Binary Search Trees II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
