一.题目
Unique Binary Search Trees II
Total Accepted: 32757 Total Submissions: 117071My Submissions
?
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.
?
Show Tags Have you met this question in a real interview? Yes No
Discuss
二.解题技巧
这道题和Unique Binary Search Trees很相似，只是这道题可能无法使用动态规划减少计算的时间，因为每一个节点的值是不一样的，不存在相同的子问题的情况，因此，计算复杂度无法下降。使用递归的方式进行的时候，时间复杂度为O(n^3)，空间复杂度为O(n)。
三.实现代码
#include
#include
#include
using std::vector; using std::unordered_map; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { private: unordered_map
> PreResult; vector
generateTrees(int n, int base) { vector
Result; if (n == 0) { TreeNode* TmpNode = NULL; Result.push_back(TmpNode); return Result; } if (n == 1) { TreeNode* TmpNode = new TreeNode(n + base); Result.push_back(TmpNode); return Result; } for (int HeadIndex = 1; HeadIndex <= n; HeadIndex++) { vector
LeftChildVector = generateTrees(HeadIndex - 1, base); vector
RightChildVector = generateTrees(n - HeadIndex, base + HeadIndex); const vector
::size_type LEFTSIZE = LeftChildVector.size(); const vector
::size_type RIGHTSIZE = RightChildVector.size(); for (vector
::size_type IndexOfLeft = 0; IndexOfLeft < LEFTSIZE; IndexOfLeft++) { for (vector
::size_type IndexOfRight = 0; IndexOfRight < RIGHTSIZE; IndexOfRight++) { TreeNode *TmpHeadNode = new TreeNode(base + HeadIndex); TmpHeadNode->left = LeftChildVector[IndexOfLeft]; TmpHeadNode->right = RightChildVector[IndexOfRight]; Result.push_back(TmpHeadNode); } } } return Result; } public: vector
generateTrees(int n) { return generateTrees(n, 0); } };
四.体会
这道题也是一个和Unique Binary Search Trees类似的问题，解题思路也比较类似，只是这个的返回是所有可能的二叉查找树，主要解答过程只是稍微修改下即可。
?