前往
大廳
主題

LeetCode - 0894. All Possible Full Binary Trees 解題心得

Not In My Back Yard | 2024-03-17 12:00:00 | 巴幣 0 | 人氣 40

題目連結:


題目意譯:
給定一整數 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 個)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作