原题链接

894. 所有可能的真二叉树 - 力扣（LeetCode）

题目解析

        给一个整数，返回所有可能的真二叉树vector<TreeNode*>类型，每棵树的val都必须为0

        真二叉树：每个节点都有零个或两个元素

---

解题思路

        要求一个含有n个节点的真二叉树，可以直接从根节点往下递归，也可以先求出一些较小数字对应的二叉树，再由较小的二叉树拼接成大叉树。

从思路上，显然第二种方法更好写一些，不过它会需要使用更多的内存空间。我这边使用的是第二种写法。

dp数组用来存放从1到n（奇数）的全部合法返回值

class Solution {
public:vector<TreeNode*> allPossibleFBT(int n) {vector<vector<TreeNode*>>dp(n + 1);dp[1] = { new TreeNode(0)};for (int i = 1; i <= n; i += 2){for (int j = 1; j < i; j += 2) {for (auto left : dp[j]){for (auto right : dp[i - j - 1]){TreeNode* tmp = new TreeNode();tmp->left = left;tmp->right = right;dp[i].push_back(tmp);}}}}return dp[n];}
};

---

关于时间复杂度和空间复杂度

        我看了几个题解，大伙差不多的解法算出来的不怎么统一，我水平不算高，就不在这班门弄斧了，（ps：力扣官方给的空间复杂度是o(1),这光dp里就有n+1个vector,属实是离谱了）。

感谢观看！！！！