首页 > 代码库 > 2 Unique Binary Search Trees II_Leetcode
2 Unique Binary Search Trees II_Leetcode
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
This is the second time I solve this problem.
Everytime when we encounter a BST problem without quite clear thought, we can resort to Divide & Conquer.
Use recursion to build the left and right subtree, then combine them then return.
In this problem, the left and right subtree can be multiple.
FIRST TRY ERROR: Forget to clear the vector of left of right subtree while apply different root.
Code:
/** * Definition for binary tree * 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) { vector<TreeNode *> res; if(n == 0) { res.push_back(NULL); return res; } res = gen(1, n); return res; } vector<TreeNode *> gen(int start, int end) { vector<TreeNode*> res; if(start == end) { TreeNode* tmp = new TreeNode(start); res.push_back(tmp); return res; } vector<TreeNode*> leftsub, rightsub; for(int i = start; i <= end; i++) { leftsub.clear(); // First try error rightsub.clear(); // First try error if(i == start) leftsub.push_back(NULL); else leftsub = gen(start, i-1); if(i == end) rightsub.push_back(NULL); else rightsub = gen(i+1, end); for(int m = 0; m < leftsub.size(); m++) { for(int n = 0; n < rightsub.size(); n++) { TreeNode* root = new TreeNode(i); // divide & conquer root->left = leftsub[m]; root->right = rightsub[n]; res.push_back(root); } } } return res; }};
2 Unique Binary Search Trees II_Leetcode