深圳网站制作 公司,网站在建设中,南京网站推广营销公司哪家好,京伦网站建设原题链接 894. 所有可能的真二叉树 - 力扣#xff08;LeetCode#xff09; 题目解析 给一个整数#xff0c;返回所有可能的真二叉树vectorTreeNode*类型#xff0c;每棵树的val都必须为0 真二叉树#xff1a;每个节点都有零个或两个元素 解题思路 要求一个含有n个…原题链接 894. 所有可能的真二叉树 - 力扣LeetCode 题目解析 给一个整数返回所有可能的真二叉树vectorTreeNode*类型每棵树的val都必须为0 真二叉树每个节点都有零个或两个元素 解题思路 要求一个含有n个节点的真二叉树可以直接从根节点往下递归也可以先求出一些较小数字对应的二叉树再由较小的二叉树拼接成大叉树。 从思路上显然第二种方法更好写一些不过它会需要使用更多的内存空间。我这边使用的是第二种写法。 dp数组用来存放从1到n奇数的全部合法返回值
class Solution {
public:vectorTreeNode* allPossibleFBT(int n) {vectorvectorTreeNode*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里就有n1个vector,属实是离谱了。 感谢观看
