Summary

I have solved 174 problems：Easy(37)、Medium(105)、Hard(32)。

leetcode_generate.py脚本改自 https://github.com/bonfy/leetcode/blob/master/leetcode_generate.py

#	Title	Source Code	Difficulty	Last submission date	Last submission url
1	two-sum	Java	Easy	2018-02-10 18:10:20	https://leetcode.com/submissions/detail/140256555/
2	add-two-numbers	Java	Medium	2019-01-11 17:44:01	https://leetcode.com/submissions/detail/200522321/
3	longest-substring-without-repeating-characters	Java	Medium	2018-02-21 18:24:58	https://leetcode.com/submissions/detail/141744296/
4	median-of-two-sorted-arrays	Java	Hard	2018-02-16 18:25:29	https://leetcode.com/submissions/detail/141081067/
5	longest-palindromic-substring	Java	Medium	2018-02-16 23:00:12	https://leetcode.com/submissions/detail/141091696/
6	zigzag-conversion	Java	Medium	2018-02-14 23:33:10	https://leetcode.com/submissions/detail/140871013/
7	reverse-integer	Java	Easy	2018-02-17 23:41:19	https://leetcode.com/submissions/detail/141194748/
8	string-to-integer-atoi	Java	Medium	2018-02-18 23:16:36	https://leetcode.com/submissions/detail/141326255/
9	palindrome-number	Java	Easy	2018-02-18 00:00:44	https://leetcode.com/submissions/detail/141195967/
10	regular-expression-matching	Java	Hard	2018-02-20 13:29:27	https://leetcode.com/submissions/detail/141572575/
11	container-with-most-water	Java	Medium	2018-02-20 15:09:08	https://leetcode.com/submissions/detail/141586207/
14	longest-common-prefix	Java	Easy	2018-02-21 15:37:19	https://leetcode.com/submissions/detail/141731052/
15	3sum	Java	Medium	2018-02-11 21:00:34	https://leetcode.com/submissions/detail/140417724/
16	3sum-closest	Java	Medium	2018-02-11 23:46:04	https://leetcode.com/submissions/detail/140428336/
17	letter-combinations-of-a-phone-number	Java	Medium	2018-02-21 21:57:16	https://leetcode.com/submissions/detail/141753043/
18	4sum	Java	Medium	2018-02-12 00:18:36	https://leetcode.com/submissions/detail/140430757/
19	remove-nth-node-from-end-of-list	Java	Medium	2018-02-21 22:29:18	https://leetcode.com/submissions/detail/141754974/
20	valid-parentheses	Java	Easy	2018-02-21 22:56:30	https://leetcode.com/submissions/detail/141756770/
21	merge-two-sorted-lists	Java	Easy	2018-02-21 20:18:13	https://leetcode.com/submissions/detail/141748396/
22	generate-parentheses	Java	Medium	2018-02-22 18:23:12	https://leetcode.com/submissions/detail/141887702/
23	merge-k-sorted-lists	Java	Hard	2018-02-22 18:46:21	https://leetcode.com/submissions/detail/141888811/
24	swap-nodes-in-pairs	Java	Medium	2018-02-22 20:31:18	https://leetcode.com/submissions/detail/141893223/
25	reverse-nodes-in-k-group	Java	Hard	2018-02-22 21:16:08	https://leetcode.com/submissions/detail/141895518/
26	remove-duplicates-from-sorted-array	Java	Easy	2018-02-22 21:31:01	https://leetcode.com/submissions/detail/141896420/
27	remove-element	Java	Easy	2018-02-22 21:39:30	https://leetcode.com/submissions/detail/141896969/
28	implement-strstr	Java	Easy	2018-02-22 22:32:31	https://leetcode.com/submissions/detail/141900320/
30	substring-with-concatenation-of-all-words	Java	Hard	2018-02-27 14:32:28	https://leetcode.com/submissions/detail/142590854/
31	next-permutation	Java	Medium	2018-02-23 12:52:35	https://leetcode.com/submissions/detail/141993157/
32	longest-valid-parentheses	Java	Hard	2018-02-24 13:52:11	https://leetcode.com/submissions/detail/142123797/
33	search-in-rotated-sorted-array	Java	Medium	2018-02-24 20:47:12	https://leetcode.com/submissions/detail/142156727/
34	find-first-and-last-position-of-element-in-sorted-array	Java	Medium	2018-02-24 21:52:23	https://leetcode.com/submissions/detail/142159882/
35	search-insert-position	Java	Easy	2018-02-24 22:07:06	https://leetcode.com/submissions/detail/142160707/
36	valid-sudoku	Java	Medium	2018-02-25 23:09:14	https://leetcode.com/submissions/detail/142316125/
37	sudoku-solver	Java	Hard	2018-02-25 23:43:48	https://leetcode.com/submissions/detail/142318388/
39	combination-sum	Java	Medium	2018-02-26 11:51:08	https://leetcode.com/submissions/detail/142409572/
40	combination-sum-ii	Java	Medium	2018-02-26 13:03:43	https://leetcode.com/submissions/detail/142420608/
41	first-missing-positive	Java	Hard	2018-02-26 13:23:42	https://leetcode.com/submissions/detail/142423486/
42	trapping-rain-water	Java	Hard	2018-02-20 16:32:08	https://leetcode.com/submissions/detail/141595380/
43	multiply-strings	Java	Medium	2018-02-13 00:49:14	https://leetcode.com/submissions/detail/140594777/
44	wildcard-matching	Java	Hard	2018-02-21 14:06:23	https://leetcode.com/submissions/detail/141718079/
45	jump-game-ii	Java	Hard	2018-02-26 17:22:20	https://leetcode.com/submissions/detail/142456566/
46	permutations	Java	Medium	2018-02-23 13:09:33	https://leetcode.com/submissions/detail/141995569/
47	permutations-ii	Java	Medium	2018-02-23 13:52:09	https://leetcode.com/submissions/detail/142001817/
48	rotate-image	Java	Medium	2018-02-26 18:24:02	https://leetcode.com/submissions/detail/142461599/
49	group-anagrams	Java	Medium	2018-02-26 19:31:42	https://leetcode.com/submissions/detail/142465441/
50	powx-n	Java	Medium	2018-02-26 20:57:01	https://leetcode.com/submissions/detail/142470818/
51	n-queens	Java	Hard	2018-02-26 22:12:41	https://leetcode.com/submissions/detail/142476557/
52	n-queens-ii	Java	Hard	2018-02-26 22:23:16	https://leetcode.com/submissions/detail/142477343/
53	maximum-subarray	Java	Easy	2018-02-26 22:33:07	https://leetcode.com/submissions/detail/142478127/
54	spiral-matrix	Java	Medium	2017-06-13 20:30:48	https://leetcode.com/submissions/detail/105911684/
55	jump-game	Java	Medium	2018-02-26 22:46:04	https://leetcode.com/submissions/detail/142479136/
56	merge-intervals	Java	Medium	2018-02-26 23:08:46	https://leetcode.com/submissions/detail/142481008/
57	insert-interval	Java	Medium	2018-02-26 23:27:24	https://leetcode.com/submissions/detail/142482489/
58	length-of-last-word	Java	Easy	2018-02-26 23:32:54	https://leetcode.com/submissions/detail/142482962/
59	spiral-matrix-ii	Java	Medium	2018-02-26 23:50:25	https://leetcode.com/submissions/detail/142484416/
61	rotate-list	Java	Medium	2018-02-27 18:49:57	https://leetcode.com/submissions/detail/142621214/
62	unique-paths	Java	Medium	2018-02-27 19:29:35	https://leetcode.com/submissions/detail/142623298/
63	unique-paths-ii	Java	Medium	2018-02-27 19:44:17	https://leetcode.com/submissions/detail/142624252/
64	minimum-path-sum	Java	Medium	2018-02-27 20:44:20	https://leetcode.com/submissions/detail/142628419/
67	add-binary	Java	Easy	2018-02-12 13:17:11	https://leetcode.com/submissions/detail/140537669/
69	sqrtx	Java	Easy	2018-02-27 23:23:26	https://leetcode.com/submissions/detail/142641624/
70	climbing-stairs	Java	Easy	2018-02-27 23:30:47	https://leetcode.com/submissions/detail/142642251/
71	simplify-path	Java	Medium	2018-02-28 00:22:32	https://leetcode.com/submissions/detail/142646998/
72	edit-distance	Java	Hard	2018-02-28 00:56:49	https://leetcode.com/submissions/detail/142650250/
73	set-matrix-zeroes	Java	Medium	2018-03-11 19:58:24	https://leetcode.com/submissions/detail/144545185/
74	search-a-2d-matrix	Java	Medium	2018-03-11 21:02:12	https://leetcode.com/submissions/detail/144550427/
75	sort-colors	Java	Medium	2018-03-11 21:16:52	https://leetcode.com/submissions/detail/144551696/
76	minimum-window-substring	Java	Hard	2018-02-28 13:46:58	https://leetcode.com/submissions/detail/142746140/
77	combinations	Java	Medium	2018-02-26 12:20:33	https://leetcode.com/submissions/detail/142413966/
79	word-search	Java	Medium	2018-03-12 23:31:30	https://leetcode.com/submissions/detail/144745335/
80	remove-duplicates-from-sorted-array-ii	Java	Medium	2018-03-16 16:51:24	https://leetcode.com/submissions/detail/145405434/
81	search-in-rotated-sorted-array-ii	Java	Medium	2018-02-24 21:06:35	https://leetcode.com/submissions/detail/142157545/
82	remove-duplicates-from-sorted-list-ii	Java	Medium	2018-03-16 17:04:12	https://leetcode.com/submissions/detail/145406815/
84	largest-rectangle-in-histogram	Java	Hard	2017-05-26 21:18:08	https://leetcode.com/submissions/detail/104078173/
85	maximal-rectangle	Java	Hard	2017-05-26 21:20:24	https://leetcode.com/submissions/detail/104078284/
86	partition-list	Java	Medium	2018-03-16 17:22:36	https://leetcode.com/submissions/detail/145408552/
88	merge-sorted-array	Java	Easy	2018-02-21 20:26:10	https://leetcode.com/submissions/detail/141748700/
91	decode-ways	Java	Medium	2018-03-01 00:37:32	https://leetcode.com/submissions/detail/142813256/
92	reverse-linked-list-ii	Java	Medium	2018-02-19 00:35:29	https://leetcode.com/submissions/detail/141331166/
94	binary-tree-inorder-traversal	Java	Medium	2018-03-08 21:08:17	https://leetcode.com/submissions/detail/144088587/
95	unique-binary-search-trees-ii	Java	Medium	2018-03-01 01:37:38	https://leetcode.com/submissions/detail/142817860/
96	unique-binary-search-trees	Java	Medium	2018-03-01 02:14:09	https://leetcode.com/submissions/detail/142820780/
97	interleaving-string	Java	Hard	2018-03-01 20:07:25	https://leetcode.com/submissions/detail/142947676/
98	validate-binary-search-tree	Java	Medium	2019-04-15 16:32:28	https://leetcode.com/submissions/detail/222569579/
100	same-tree	Java	Easy	2018-05-02 16:46:56	https://leetcode.com/submissions/detail/152475735/
101	symmetric-tree	Java	Easy	2018-03-18 01:10:34	https://leetcode.com/submissions/detail/145579300/
102	binary-tree-level-order-traversal	Java	Medium	2018-05-02 18:03:14	https://leetcode.com/submissions/detail/152481386/
103	binary-tree-zigzag-level-order-traversal	Java	Medium	2018-05-02 17:41:15	https://leetcode.com/submissions/detail/152480055/
104	maximum-depth-of-binary-tree	Java	Easy	2018-05-02 18:20:26	https://leetcode.com/submissions/detail/152482232/
105	construct-binary-tree-from-preorder-and-inorder-traversal	Java	Medium	2018-03-09 19:23:16	https://leetcode.com/submissions/detail/144241601/
106	construct-binary-tree-from-inorder-and-postorder-traversal	Java	Medium	2018-03-09 19:10:40	https://leetcode.com/submissions/detail/144240866/
107	binary-tree-level-order-traversal-ii	Java	Medium	2018-05-02 18:53:01	https://leetcode.com/submissions/detail/152483674/
110	balanced-binary-tree	Java	Easy	2018-03-18 16:16:51	https://leetcode.com/submissions/detail/145703003/
111	minimum-depth-of-binary-tree	Java	Easy	2019-04-26 13:31:53	https://leetcode.com/submissions/detail/225029896/
112	path-sum	Java	Easy	2018-05-02 19:00:42	https://leetcode.com/submissions/detail/152484081/
113	path-sum-ii	Java	Medium	2018-05-06 19:50:28	https://leetcode.com/submissions/detail/153028293/
114	flatten-binary-tree-to-linked-list	Java	Medium	2018-01-28 01:17:51	https://leetcode.com/submissions/detail/138127587/
115	distinct-subsequences	Java	Hard	2018-03-01 21:11:13	https://leetcode.com/submissions/detail/142952536/
116	populating-next-right-pointers-in-each-node	Java	Medium	2018-05-06 20:47:19	https://leetcode.com/submissions/detail/153031879/
117	populating-next-right-pointers-in-each-node-ii	Java	Medium	2018-05-06 21:34:03	https://leetcode.com/submissions/detail/153035124/
120	triangle	Java	Medium	2018-03-02 16:13:47	https://leetcode.com/submissions/detail/143081489/
121	best-time-to-buy-and-sell-stock	Java	Easy	2018-03-02 03:16:25	https://leetcode.com/submissions/detail/142983794/
122	best-time-to-buy-and-sell-stock-ii	Java	Easy	2018-03-02 03:41:21	https://leetcode.com/submissions/detail/142986466/
123	best-time-to-buy-and-sell-stock-iii	Java	Hard	2018-03-02 04:22:32	https://leetcode.com/submissions/detail/142990620/
124	binary-tree-maximum-path-sum	Java	Hard	2018-05-10 00:05:09	https://leetcode.com/submissions/detail/153500021/
128	longest-consecutive-sequence	Java	Hard	2019-01-13 18:00:35	https://leetcode.com/submissions/detail/200922373/
129	sum-root-to-leaf-numbers	Java	Medium	2018-05-10 14:31:49	https://leetcode.com/submissions/detail/153596769/
130	surrounded-regions	Java	Medium	2019-01-11 21:35:53	https://leetcode.com/submissions/detail/200539347/
131	palindrome-partitioning	Java	Medium	2018-03-02 21:02:04	https://leetcode.com/submissions/detail/143100316/
132	palindrome-partitioning-ii	Java	Hard	2018-03-02 22:56:42	https://leetcode.com/submissions/detail/143107667/
139	word-break	Java	Medium	2018-03-02 23:26:11	https://leetcode.com/submissions/detail/143109830/
140	word-break-ii	Java	Hard	2018-03-04 00:41:03	https://leetcode.com/submissions/detail/143243070/
142	linked-list-cycle-ii	Java	Medium	2019-01-13 20:10:59	https://leetcode.com/submissions/detail/200932462/
144	binary-tree-preorder-traversal	Java	Medium	2018-03-08 21:13:15	https://leetcode.com/submissions/detail/144089104/
145	binary-tree-postorder-traversal	Java	Medium	2018-03-08 21:20:26	https://leetcode.com/submissions/detail/144089853/
146	lru-cache	Java	Medium	2018-03-20 18:48:14	https://leetcode.com/submissions/detail/146064526/
147	insertion-sort-list	Java	Medium	2018-03-13 00:53:05	https://leetcode.com/submissions/detail/144753529/
152	maximum-product-subarray	Java	Medium	2018-03-02 16:50:29	https://leetcode.com/submissions/detail/143085677/
153	find-minimum-in-rotated-sorted-array	Java	Medium	2018-02-24 16:55:17	https://leetcode.com/submissions/detail/142143759/
154	find-minimum-in-rotated-sorted-array-ii	Java	Hard	2018-02-24 20:07:03	https://leetcode.com/submissions/detail/142154970/
155	min-stack	Java	Easy	2018-02-28 15:01:23	https://leetcode.com/submissions/detail/142759537/
167	two-sum-ii-input-array-is-sorted	Java	Easy	2018-02-10 18:52:24	https://leetcode.com/submissions/detail/140258540/
173	binary-search-tree-iterator	Java	Medium	2018-05-02 16:42:14	https://leetcode.com/submissions/detail/152475310/
174	dungeon-game	Java	Hard	2018-02-27 22:49:16	https://leetcode.com/submissions/detail/142638726/
188	best-time-to-buy-and-sell-stock-iv	Java	Hard	2018-03-02 15:38:16	https://leetcode.com/submissions/detail/143076695/
198	house-robber	Java	Medium	2018-03-04 23:48:59	https://leetcode.com/submissions/detail/143405166/
199	binary-tree-right-side-view	Java	Medium	2018-05-10 14:52:19	https://leetcode.com/submissions/detail/153599592/
200	number-of-islands	Java	Medium	2018-03-25 21:10:14	https://leetcode.com/submissions/detail/146871687/
206	reverse-linked-list	Java	Easy	2018-02-18 23:46:34	https://leetcode.com/submissions/detail/141328078/
213	house-robber-ii	Java	Medium	2018-03-05 00:32:03	https://leetcode.com/submissions/detail/143408812/
214	shortest-palindrome	Java	Hard	2018-02-17 23:09:52	https://leetcode.com/submissions/detail/141193041/
215	kth-largest-element-in-an-array	Java	Medium	2019-07-13 16:28:02	https://leetcode.com/submissions/detail/242950891/
222	count-complete-tree-nodes	Java	Medium	2018-03-12 23:50:18	https://leetcode.com/submissions/detail/144747413/
226	invert-binary-tree	Java	Easy	2018-03-18 01:01:01	https://leetcode.com/submissions/detail/145578358/
230	kth-smallest-element-in-a-bst	Java	Medium	2018-03-18 15:17:06	https://leetcode.com/submissions/detail/145696051/
234	palindrome-linked-list	Java	Easy	2018-02-18 23:42:21	https://leetcode.com/submissions/detail/141327809/
235	lowest-common-ancestor-of-a-binary-search-tree	Java	Easy	2018-03-08 16:20:59	https://leetcode.com/submissions/detail/144062614/
236	lowest-common-ancestor-of-a-binary-tree	Java	Medium	2020-07-29 19:37:13	https://leetcode.com/submissions/detail/373159729/
239	sliding-window-maximum	Java	Hard	2018-02-28 14:40:30	https://leetcode.com/submissions/detail/142755722/
240	search-a-2d-matrix-ii	Java	Medium	2018-03-11 21:07:59	https://leetcode.com/submissions/detail/144550939/
257	binary-tree-paths	Java	Easy	2018-05-10 15:59:54	https://leetcode.com/submissions/detail/153607469/
263	ugly-number	Java	Easy	2018-04-04 17:54:19	https://leetcode.com/submissions/detail/148464199/
264	ugly-number-ii	Java	Medium	2018-04-05 00:03:37	https://leetcode.com/submissions/detail/148490711/
268	missing-number	Java	Easy	2018-02-26 13:56:08	https://leetcode.com/submissions/detail/142428274/
279	perfect-squares	Java	Medium	2018-04-10 19:45:52	https://leetcode.com/submissions/detail/149378260/
287	find-the-duplicate-number	Java	Medium	2018-02-26 18:40:41	https://leetcode.com/submissions/detail/142462594/
300	longest-increasing-subsequence	Java	Medium	2018-02-28 15:47:51	https://leetcode.com/submissions/detail/142767120/
303	range-sum-query-immutable	Java	Easy	2018-05-30 18:36:57	https://leetcode.com/submissions/detail/156549550/
304	range-sum-query-2d-immutable	Java	Medium	2018-01-22 22:00:59	https://leetcode.com/submissions/detail/137348080/
322	coin-change	Java	Medium	2019-04-11 16:15:08	https://leetcode.com/submissions/detail/221650701/
337	house-robber-iii	Java	Medium	2018-03-05 01:14:50	https://leetcode.com/submissions/detail/143412400/
343	integer-break	Java	Medium	2018-03-24 18:03:03	https://leetcode.com/submissions/detail/146689436/
347	top-k-frequent-elements	Java	Medium	2018-08-21 23:48:00	https://leetcode.com/submissions/detail/170811643/
354	russian-doll-envelopes	Java	Hard	2018-02-28 20:45:13	https://leetcode.com/submissions/detail/142792816/
371	sum-of-two-integers	Java	Medium	2018-02-12 11:42:16	https://leetcode.com/submissions/detail/140523546/
376	wiggle-subsequence	Java	Medium	2018-03-24 18:28:27	https://leetcode.com/submissions/detail/146690864/
378	kth-smallest-element-in-a-sorted-matrix	Java	Medium	2018-03-19 07:55:54	https://leetcode.com/submissions/detail/145801668/
407	trapping-rain-water-ii	Java	Hard	2018-02-21 13:47:04	https://leetcode.com/submissions/detail/141715106/
445	add-two-numbers-ii	Java	Medium	2018-02-12 14:05:38	https://leetcode.com/submissions/detail/140544910/
454	4sum-ii	Java	Medium	2018-02-12 11:12:08	https://leetcode.com/submissions/detail/140518628/
491	increasing-subsequences	Java	Medium	2018-03-09 20:55:20	https://leetcode.com/submissions/detail/144247554/
539	minimum-time-difference	Java	Medium	2018-02-21 15:15:32	https://leetcode.com/submissions/detail/141728222/
547	number-of-provinces	Java	Medium	2019-01-13 18:42:36	https://leetcode.com/submissions/detail/200925787/
563	binary-tree-tilt	Java	Easy	2018-05-02 17:05:15	https://leetcode.com/submissions/detail/152477334/
583	delete-operation-for-two-strings	Java	Medium	2018-02-28 01:36:08	https://leetcode.com/submissions/detail/142653996/
646	maximum-length-of-pair-chain	Java	Medium	2018-02-28 20:19:19	https://leetcode.com/submissions/detail/142791083/
653	two-sum-iv-input-is-a-bst	Java	Easy	2018-02-10 19:31:41	https://leetcode.com/submissions/detail/140260025/
673	number-of-longest-increasing-subsequence	Java	Medium	2018-02-28 18:12:00	https://leetcode.com/submissions/detail/142783323/
684	redundant-connection	Java	Medium	2019-01-13 19:11:56	https://leetcode.com/submissions/detail/200928137/
695	max-area-of-island	Java	Medium	2018-03-26 13:15:25	https://leetcode.com/submissions/detail/146995937/
712	minimum-ascii-delete-sum-for-two-strings	Java	Medium	2018-02-28 13:15:34	https://leetcode.com/submissions/detail/142741084/
747	min-cost-climbing-stairs	Java	Easy	2018-02-27 23:53:32	https://leetcode.com/submissions/detail/142644338/
778	reorganize-string	Java	Medium	2018-02-21 21:17:48	https://leetcode.com/submissions/detail/141750948/
993	tallest-billboard	Java	Hard	2018-12-14 21:34:59	https://leetcode.com/submissions/detail/195067385/

Detail

1.两数之和

solution1

最直观暴力原生的做法，遍历每个位置i, 看是否有j能够和它组成一个和。

for(int i=0; i< arr.length; i++){
    for(j=i+1; j< arr.length; j++){
        if(arr[i] = arr[j] == sum){
            return (i,j);
        }
    }
}

时间复杂度O(n*n), 空间复杂度O(1)

solution2(prefer)

遍历每一个位置i,看前面是否出现过值sum-arr[i], 如果有，则找到了两数只和。过程中需要借助一个map维护value->index的映射。

function int[] twoSum(int[] arr, int target){
    int[] res = new int[2];
    Map<Integer,Integer> map= new HashMap<>();
    for(int i=0; i< arr.length; i++){
        if(map.contains(target - arr[i])){      
            res[0] = map.get(target - arr[i]);
            res[1] = i;
            return res;
        }
        map.put(arr[i],i);
    }
    return res;
}

solution3

如果输入是一个有序列表，那么可以用双指针夹逼。时间复杂度O(n),空间复杂度O(1)。

function int[] twoSum(int[] arr, int target){
    int start = 0;
    int end = arr.length -1;
    while(start > end){
        if(arr[start] + arr[end] == target){
            return (start,end); 
        }
        if(arr[start] + arr[end] > target){
            start++;
        }else {
            end --;
        }
    }
}

如果输入非有序列表，那么可以先排序O(nLogn), 在执行如上算法。总体时间复杂度O(nLogn)， 空间复杂度O(n)

91. 二叉搜索树构成种类

对于任意一个数字i，根据BST树的性质，比i小的数字都应该在左边，比i大的数字都应在在右边。因此，可以枚举每一个root节点, 对于每一个root节点i，countBSTs(1,n) = countBSTs(1,i-1) * countBSTs(i+1,n), 因此就递归拆机成了两个子问题。

int countBST(int start, int end){
    if(start > end){
        return 0;
    }
    if(start == end){
        1;
    }
    int count =0;
    for(int i=start; i <= end ; i++){
        count += countBST(start, i-1) * countBST(i+1, end);
    }
    return count;
}

画个图，中间存在重复子过程，因此需要保存运算保证中的中间结果--> 带备忘录的递归。