二元樹算是目前遇到稍微棘手級別,棘手級別目前只有莫隊算法,還沒有花時間去弄通它。
這一題屬於「遞迴」的範圍之內,給一個數字,要你回傳有相同節點數的所有可能。
一開始直覺,就是把數列排序,取一個數字,由於是二元樹,左邊皆小於該節值,右邊則大於,所以左邊樹結就是該數字左邊的所有項目組合,右邊等同處理。
接下來,要設一個節點,該節點左邊的等於左邊的遞迴結果,右邊等同處理。
就在這裡卡了一整個下午,之前相關的遞迴幾乎是把 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)