題目連結:
題目意譯:
給定一整數 n,回傳一個裝著所有由 n 個節點所組成的滿二元樹之列表。答案中每棵樹的每一個節點 Node 應滿足 Node.val == 0。
答案中每一個元素為一種可能的樹之根節點。你可以按任意順序排列這些答案。
一個滿二元樹一棵樹,其中每一個節點只有恰好 0 個或 2 個小孩。
限制:
1 ≦ n ≦ 20
範例測資:
範例 1:
輸入: n = 7
輸出: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
範例 2:
輸入: n = 3
輸出: [[0,0,0]]
解題思維:
就遞迴窮舉:
「左邊分配 1 個節點、右邊分配 n - 2 個節點」、
「左邊分配 2 個節點、右邊分配 n - 3 個節點」、
……
「左邊分配 n - 3 個節點、右邊分配 2 個節點」、
「左邊分配 n - 2 個節點、右邊分配 1 個節點」
然後用若干個「根節點」把左右兩邊分配節點後回傳的結果合併即可(如果左邊有 L 個、右邊有 R,則合併後應為 L × R 個)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。