※ 引述《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;
}
};