輸出1-n數字組成的所有二叉搜索樹，遞歸+dp，用python3的話還可以加lru_cache
C++
1 //95
2 //Runtime: 128 ms (Beats 7.1%)
3
4 /**
5 * Definition for binary tree
6 * struct TreeNode {
7 * int val;
8 * TreeNode *left;
9 * TreeNode *right;
10 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 * };
12 */
13 class Solution {
14 public:
15 vector<TreeNode *> sov(int l, int r) {
16 vector<TreeNode *> ans;
17 if(l > r) ans.push_back(NULL);
18 else {
19 for(int i = l; i <= r; ++i) {
20 vector<TreeNode *> left = sov(l, i - 1);
21 vector<TreeNode *> right = sov(i + 1, r);
22 for(int ll = 0; ll < left.size(); ++ll) {
23 for(int rr = 0; rr < right.size(); ++rr) {
24 TreeNode *root = new TreeNode(i);
25 root->left = left[ll];
26 root->right = right[rr];
27 ans.push_back(root);
28 }
29 }
30 }
31 }
32 return ans;
33 }
34
35 vector<TreeNode *> generateTrees(int n) {
36 return sov(1, n);
37 }
38 };
Python
1 #95
2 #Runtime: 38 ms (Beats 79.12%)
3 #Memory: 16.2 MB (Beats 63.19%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def generateTrees(self, n):
13 """
14 :type n: int
15 :rtype: List[TreeNode]
16 """
17
18 def dp(l, r):
19 if l > r:
20 return [None]
21 ans = []
22 for i in range(l, r + 1):
23 l_tree = dp(l, i - 1)
24 r_tree = dp(i + 1, r)
25 for ll in l_tree:
26 for rr in r_tree:
27 root = TreeNode(i)
28 root.left = ll
29 root.right = rr
30 ans.append(root)
31 return ans
32 return dp(1, n)