Unique Binary Search Trees II问题及解法

本文主要是介绍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问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---