本文主要是介绍Unique Binary Search Trees II问题及解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
示例：
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
问题分析：
本题要求构建[1...n]的BST，根据BST的性质，构建树可以分为构建根节点、构建左子树和构建右子树，显然这是一种子问题划分，属于动态规划范畴。
过程详见代码：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<TreeNode*> generateTrees(int n) {if(!n) return vector<TreeNode*>();return createTree(1, n);}vector<TreeNode *> createTree(int start, int end){vector<TreeNode *> results;if (start>end){results.push_back(NULL);return results;}for (int k = start; k <= end; k++){vector<TreeNode *> left = createTree(start, k - 1);vector<TreeNode *> right = createTree(k + 1, end);for (int i = 0; i<left.size(); i++){for (int j = 0; j<right.size(); j++){TreeNode * root = new TreeNode(k);root->left = left[i];root->right = right[j];results.push_back(root);}}}return results;}
};这篇关于Unique Binary Search Trees II问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
