由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - generate all distinct full binary trees with n leaves
相关主题
full or complete binary tree的问题请问一个简单的面试题
amazon一道面试题amazon first phone interview, rejected
问道题,binary tree里有一个有indegree 2How many different binary trees are possible with n nodes ?
Lowest common ancestor of two nodes of Binary Tree判断 bst 疑问
上几个面经顺求Blessnon recursive binary tree traversal in O(n) time and O(1) space
求教一道老题一道大公司诡异的complete binary tree max sum of 2 nodes 题
这个Binary Tree的题来看看问个binary tree node path的概念问题
讨论个Binary search tree的题目问个amazon面试题
相关话题的讨论汇总
话题: leaves话题: trees话题: distinct话题: binary话题: full
进入JobHunting版参与讨论
1 (共1页)
s**1
发帖数: 71
1
大家好
有道binary Tree 的题请教大家,generate all structurally distinct full binary
trees with n leaves, "full" means all internal (non-leaf) nodes have
exactly two children. For example, there are 5 distinct full binary trees
with 4 leaves each.
着重想问下 如何用DP解决呢?
多谢多谢!
x***y
发帖数: 633
2
Let F(n, k) to be # of different structures with n leaves and k leaves in
the lowest level. k must be even to be valid.
F(n, k) =
sum{ k/2 <= i <= n-k/2 and i is even } F(n-k/2, i) C(i, k/2)
with F(j, j) = 1 when j is power of 2
and F(j, j) is invalid if not.
For your example, it's F(4,4)+F(4,2)
F(4,4) =1
F(4,2) = F(3, 2) C(2, 1) = F(2,2)C(2,1)C(2,1) = 4
So totaly 5.
s**1
发帖数: 71
3
Thank you so much. Would you please walk me through the algorithm a little,
because the hardest part k/2 <= i <= n-k/2 I haven't figured out.
Thanks again.
In addition, if I want to print out all the trees in dotted parenthesized
form, recursion is a good way? Or iterator? I have no clue on that? Can you
please give me some hint?
Thanks again.

【在 x***y 的大作中提到】
: Let F(n, k) to be # of different structures with n leaves and k leaves in
: the lowest level. k must be even to be valid.
: F(n, k) =
: sum{ k/2 <= i <= n-k/2 and i is even } F(n-k/2, i) C(i, k/2)
: with F(j, j) = 1 when j is power of 2
: and F(j, j) is invalid if not.
: For your example, it's F(4,4)+F(4,2)
: F(4,4) =1
: F(4,2) = F(3, 2) C(2, 1) = F(2,2)C(2,1)C(2,1) = 4
: So totaly 5.

i***h
发帖数: 12655
4
F(n) = F(1)*F(n-1) + F(2)*F(n-2) + ... + F(k)*F(n-k) + ...
s**1
发帖数: 71
5
Thank you All.
Allow me to summarize the Dynamic Programming:
Let T(n) be the number of distinct full trees and n the parameter for the
number of leaves
So T(n) = T(n-1)*T(1)+T(n-2)*T(2)+...+T(2)*T(n-2)+T(1)*T(n-1)
and T(1)=1 T(2)=1
Thus, build up a table first, lookup the table if there is we want then use
it, if not update the table for the future use.
1 (共1页)
进入JobHunting版参与讨论
相关主题
问个amazon面试题上几个面经顺求Bless
弱问怎么判断两个binary tree相同?求教一道老题
recover binary search tree 常数空间这个Binary Tree的题来看看
binary tree, sum of 2 nodes == given number讨论个Binary search tree的题目
full or complete binary tree的问题请问一个简单的面试题
amazon一道面试题amazon first phone interview, rejected
问道题,binary tree里有一个有indegree 2How many different binary trees are possible with n nodes ?
Lowest common ancestor of two nodes of Binary Tree判断 bst 疑问
相关话题的讨论汇总
话题: leaves话题: trees话题: distinct话题: binary话题: full