今天碰到這一題，卡關很久，來記錄一下。
二元樹算是目前遇到稍微棘手級別，棘手級別目前只有莫隊算法，還沒有花時間去弄通它。
這一題屬於「遞迴」的範圍之內，給一個數字，要你回傳有相同節點數的所有可能。
一開始直覺，就是把數列排序，取一個數字，由於是二元樹，左邊皆小於該節值，右邊則大於，所以左邊樹結就是該數字左邊的所有項目組合，右邊等同處理。
接下來，要設一個節點，該節點左邊的等於左邊的遞迴結果，右邊等同處理。
就在這裡卡了一整個下午，之前相關的遞迴幾乎是把 node 往下傳，然後回傳也是 node。如果node 傳下來，左右邊的有數種組合，但是根節點只有一個，左邊要哪一個組合？右邊要哪一個組合？還是一開始就傳許多根節？直接以根結點指定左右是不可行的。
由上而下的想法是行不通的，這題需要的是由下而上。但一開始的想法碰壁之後就一直在思考由上而下的想法，直到最後才又回歸一開始的寫法改進。
既然有各種組合，就不能回傳節點，要能涵蓋各種組合，首選是用串列。
將回傳改成串列，左右邊會各有一個串列包含數種組合，最後再左右合併，往頭傳遞。這點順利改好後，一切就順多了。
用兩個迴圈跑完所有的左右組合，這時才把該子二元樹根節實例化，就不會有共同祖先的問題，也能產出對應數量且沒有重疊的子二元樹根節。
如果左或右沒有組合，就需要換成一個 [None] 來代替，沒有組合的那邊就只會是 None 也算一種組合。
寫完整理後就如下：
class Solution:
def generateTrees(self, n: int):
def nextNode(ns):
NTS = []
for i in range(len(ns)):
lntree = nextNode(ns[:i])
rntree = nextNode(ns[i+1:])
if not lntree: lntree = [None]
if not rntree: rntree = [None]
for l in lntree:
for r in rntree:
root = TreeNode(ns[i])
root.left, root.right = l, r
NTS.append(root)
return NTS
return nextNode(list(range(1,n+1)))
相當地直觀，但是效率並不到前中段班的。
前段班在代碼中加上 memo，將組合儲存起來，如果有就優先返回該值，沒有才遞迴並建立。
在一個區間的組合是固定的，就像1234組合起來，只會有同一種各組合可能。根如果為5、6、7…，1234就會被重複計算到，有memo就不用再算一次。
索引就以左界右界，建立二維串列儲存。
class Solution:
def generateTrees(self, n: int):
memo = [[None]*n for _ in range(n)]
def nextNode(l, r):
if l > r: return [None]
elif memo[l][r]: return memo[l][r]
NTS = []
for i in range(l,r+1, 1):
print(l, i, i+1, r,range(l,r+1, 1))
lntree = nextNode(l, i-1)
rntree = nextNode(i+1, r)
for lt in lntree:
for rt in rntree:
root = TreeNode(i+1)
root.left, root.right = lt, rt
NTS.append(root)
memo[l][r] = NTS
return NTS
if n == 0: return []
return nextNode(0, n-1)