算法练习----力扣每日一题------5

原题链接

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,属实是离谱了）。

感谢观看！！！！