上海好的网站制作公司,苏州网站建设报价单,wordpress编辑颜色,电商推广技巧题目详见https://leetcode.cn/problems/all-possible-full-binary-trees/
主搞动态规划#xff0c;因为这玩意儿我还不是很懂
关于节点个数为奇数偶数的证明请见官方题解方法一中的如下内容#xff1a;
这里DP的一个主要思想是#xff1a;对于任何一个满二叉树#xff…题目详见https://leetcode.cn/problems/all-possible-full-binary-trees/
主搞动态规划因为这玩意儿我还不是很懂
关于节点个数为奇数偶数的证明请见官方题解方法一中的如下内容
这里DP的一个主要思想是对于任何一个满二叉树如果我们去掉根节点那么剩下的部分就是两个更小的满二叉树。因此我们可以通过将更小的满二叉树组合在一起来生成更大的满二叉树。
这就是为什么在代码中有两个嵌套的循环。外层循环遍历所有的 i代表我们想要生成的满二叉树的节点数量。内层循环遍历所有的 j代表左子树的节点数量。因为满二叉树的节点总数必须是奇数每个非叶节点都有两个子节点所以 i 和 j 都是以 2 的步长增加的对于每个 j代码会遍历 dp[j] 和 dp[i-1-j] 中的所有可能的左子树和右子树。然后它会创建一个新的满二叉树其左子树和右子树分别是当前的左子树和右子树然后将这个新的满二叉树添加到 dp[i] 中。
光看也不好理解这里提供 n7 的时候最后的dp数组的样子
{ 此处偶数位为空, // dp[0] {[0]}, // dp[1] 此处偶数位为空, // dp[2] {[0,0,0]}, // dp[3], 这里不要数数组的长度而要数节点(0)的个数 此处偶数位为空, {[0,0,0,null,null,0,0], [0,0,0,0,0]}, // dp[5] 此处偶数位为空, {[0,0,0,null,null,0,0,null,null,0,0], [0,0,0,null,null,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,null,null,null,null,0,0], [0,0,0,0,0,null,null,0,0]} // dp[7] }
大家可以试试使用 d p [ a ] 0 ( 这是个节点 ) d p [ b ] dp[a] 0(这是个节点) dp[b] dp[a]0(这是个节点)dp[b] 来拼 d p [ a b 1 ] dp[ab1] dp[ab1]比如使用 d p [ 1 ] 0 ( 这是个节点 ) d p [ 5 ] dp[1] 0(这是个节点) dp[5] dp[1]0(这是个节点)dp[5] 来拼 d p [ 7 ] dp[7] dp[7] 笔者也在新手学习期中所写的内容主要与大家交流学习使用如有发现任何问题敬请指正
