※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 思路：
: 1.因為要構建所有樹的可能，所以只能用dfs去遞迴所有結果，所以關鍵在遞迴結束條件。
: 2.一個 full BT 的子節點數量只能為 0 或 2 這表示當 n 為偶數時，不可能存在合法
: 的樹，返回空的 List。
: 3.full BT 的最小合法樹為 n = 1 只有根節點的情況，所以 n = 1 也直接返回。
: 4.當 n 為奇數時，我們可以先把根節點設置好，並把剩下的節點分給左右子樹去遞迴構
: 建，構建結果的左右子樹組合就是解。
Tree每次都要玩遞迴
好苦
這題主要是FBT的特性 可以只有左node不能只有右node
1. 先排除掉node偶數以及n=1的情況
2. 以及右側tree的數量是 n - 左側數量 - 1(root那個點)
3. 每次迴圈跑i都是在定義左邊tree有幾個，然後才考慮右邊tree的情況
最後就是一直家庭代工 把Tree接起來
class Solution
{
public:
vector<TreeNode*> allPossibleFBT(int n)
{
if (n % 2 == 0)
return {};
if (n == 1)
return { new TreeNode(0) };
vector<TreeNode*> result;
for (int i = 1; i < n; i += 2)
{
int j = n - 1 - i;
vector<TreeNode*> left_tree = allPossibleFBT(i);
vector<TreeNode*> right_tree = allPossibleFBT(j);
for (auto left_node : left_tree)
{
for (auto right_node : right_tree)
{
auto node = new TreeNode(0);
node->left = left_node;
node->right = right_node;
result.push_back(node);
}
}
}
return result;
}
};