推 killheken: 大師 07/23 14:23
→ yam276: 大師 07/23 16:18
https://leetcode.com/problems/all-possible-full-binary-trees/description/
894. All Possible Full Binary Trees
給你一個數字 n ，找出所有合法的Full Binary Trees，他被定義為所有子節點個數
都是 0 或 2。
Example 1:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/22/fivetrees.png
Input: n = 7
Output:
[[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]]
Example 2:
Input: n = 3
Output: [[0,0,0]]
思路：
1.因為要構建所有樹的可能，所以只能用dfs去遞迴所有結果，所以關鍵在遞迴結束條件。
2.一個 full BT 的子節點數量只能為 0 或 2 這表示當 n 為偶數時，不可能存在合法
的樹，返回空的 List。
3.full BT 的最小合法樹為 n = 1 只有根節點的情況，所以 n = 1 也直接返回。
4.當 n 為奇數時，我們可以先把根節點設置好，並把剩下的節點分給左右子樹去遞迴構
建，構建結果的左右子樹組合就是解。
Java Code：
-------------------------------------------------------
class Solution {
public List<TreeNode> allPossibleFBT(int n) {
List<TreeNode> res = new ArrayList<>();
if (n == 2) {
return res;
}
if (n == 1) {
res.add(new TreeNode());
return res;
}
for (int left = 1, right = n - 2; left < n; left++, right--) {
List<TreeNode> leftChildren = allPossibleFBT(left);
List<TreeNode> rightChildren = allPossibleFBT(right);
for (TreeNode leftChild : leftChildren) {
for (TreeNode rightChild : rightChildren) {
TreeNode root = new TreeNode(0, leftChild, rightChild);
res.add(root);
}
}
}
return res;
}
}
-------------------------------------------------------
--
https://i.imgur.com/DANRJFR.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690088536.A.A3B.html
※ 編輯: Rushia (122.100.75.86 臺灣), 07/23/2023 13:57:51