动态规划算法
二叉树 T 是半平衡的，如果对于 T 中的每个节点 m：
R(m)/2 <= L(m) <= 2*R(m)，
其中 L(m) 是 T 中的节点数m 的左子树，R(m) 是 m 的右子树中的节点数。
(a) 写一个递推关系来统计N个半平衡二叉树的数量 节点。
(b) 提供用于计算 (a) 中的递推的动态规划算法。
我该如何为此建立递归关系？
以下情况是否合格？
if(node==NULL)
return;
if(given relation is true)
count++
else find for right tree;
find for left tree;
我猜他问的更多的是递归关系，比如函数之类的。？
另外，我该如何使用动态规划来解决这个问题？我想如果我应用上面建议的代码片段，我不需要存储任何东西。
请帮忙。
A binary tree T is semi-balanced if for every node m in T:
R(m)/2 <= L(m) <= 2*R(m),
where L(m) is the number of nodes in the left-sub-tree of m and R(m) is the number of nodes in the right-sub-tree of m.
(a) Write a recurrence relation to count the number of semi-balanced binary trees with N
nodes.
(b) Provide a Dynamic Programming algorithm for computing the recurrence in (a).
How do i go about making the recurrence relation for this?
Does the following qualify?
if(node==NULL)
return;
if(given relation is true)
count++
else find for right tree;
find for left tree;
I guess he is asking more of a recurrence relation like a function or something.?
Also how do i go about doing the problem using dynamic programming? I guess i dont need to store anything if i apply the above suggested code snippet.
Kindly help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
提示：设
C(n)为具有n个节点的半平衡树的数量。如果您知道C(1)、C(2)、...、C(n)的值，则可以轻松计算C(n+1)取根节点，并根据规定的条件将剩余的n个节点划分为左子树和右子树。子树中的节点数量可以从
n/3到2*n/3，因为这些值满足条件R(n)/2R(n)/2R(n)/2R(n)/2R(n)/2R(n)/2 = L(n) <= 2*R(n)。更新：
C(n) = 从 n/3 到 2n/3 L(n)*R(n) 的总和Hint: Let
C(n)be number of semi-balanced trees withnnodes. If you know values forC(1), C(2), ..., C(n)than it is easy to calculateC(n+1)by taking root node and dividing remainingnnodes into left and right sub-trees by condition stated.Number of nodes in sub-trees can be from
n/3to2*n/3, since these values satisfy conditionR(n)/2 <= L(n) <= 2*R(n).Update:
C(n) = sum from n/3 to 2n/3 L(n)*R(n)