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迄今為止看到的最為經典的算法,分數超過14000的好評 最經典的解法:
/** * 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 generateTrees(int n) { return helper(1, n); } vector helper(int s, int e){ if(s>e){ return vector(1, NULL); } vector res; for(int i=s; i<=e; i++){ vector left=helper(s, i-1); vector right=helper(i+1, e); for(int j=0; jleft=left[j]; p->right=right[k]; res.push_back(p); } } } return res; } };