s****a
发帖数: 46 | 1 不知道是不是旧题，在版面上没搜到。
how many different binary trees you can build with N nodes? For example, one
node: 1 tree; 2 nodes: 2 trees; 3 nodes: 5 trees...
面试的时候没想起来怎么做时间就到了，很是郁闷。 |
c**********r
发帖数: 472 | |
k*k
发帖数: 49 | |
s**9
发帖数: 207 | 4 面试中能给出 N(i)=sum(N(j)*N(i-1-j), j=0..i-1) 估摸着够了吧
【在 k*k 的大作中提到】
: catalan number:
: http://en.wikipedia.org/wiki/Catalan_number
|
k***e
发帖数: 556 | 5 99.9%够了
不够只可能是你碰到一个专门搞combinatorics的 对于生成函数之类的特别熟练
然后看你很不爽 非要你现场推导公式
【在 s**9 的大作中提到】
: 面试中能给出 N(i)=sum(N(j)*N(i-1-j), j=0..i-1) 估摸着够了吧
|
w******1
发帖数: 520 | |
s**9
发帖数: 207 | 7 你，推出来的？
【在 w******1 的大作中提到】
: (1/n+1) * C(n,2n)
|
w******1
发帖数: 520 | 8 GOOGLE 出来的， ALGORITHM 教材有总结的吧。
【在 s**9 的大作中提到】
: 你，推出来的？
|
s****a
发帖数: 46 | 9 我问面试官是推导出一个公式吗，他说用一个公式表示可能比较困难，他还让我写code
来计算看组成的binary tree树，提示我用递归。我想了半天也也没想出来怎么用递归
。哪位牛人可以指点一下吗？
【在 k***e 的大作中提到】
: 99.9%够了
: 不够只可能是你碰到一个专门搞combinatorics的 对于生成函数之类的特别熟练
: 然后看你很不爽 非要你现场推导公式
|
l*******m
发帖数: 18 | 10 把结果显式的写出来挺麻烦
写出递归函数很容易
你CLRS还没有吃透 回去看看矩阵相乘的dp算法和书后练习
code
【在 s****a 的大作中提到】
: 我问面试官是推导出一个公式吗，他说用一个公式表示可能比较困难，他还让我写code
: 来计算看组成的binary tree树，提示我用递归。我想了半天也也没想出来怎么用递归
: 。哪位牛人可以指点一下吗？
|
|
|
m*****g
发帖数: 226 | 11 是否可以这样递归
如果n node form T(n) binary trees，
T(n+1) 便在T(n)上面加一个。
从most unbalanced binary tree, n nodes, n possible positions to add
到most balanced binary tree, n nodes, 0 possible positions to add
是不是T(n+1)=T(n)+(n-1+n-2+...+1)
这样搞？ |
d****i
发帖数: 4354 | 12 It is not hard :
def T(n):
if n == 0: return 1
if n == 1: return 1
sub_nodes_total = n - 1
combination_count = 0
for i in xrange(0, n): # i iterated from 0 to (n - 1)
left_node_count = i
right_node_count = sub_nodes_total - i
left_combination_count = T(i) # combination count of left sub tree
right_combination_count = T(right_node_count) # combination count of right sub tree
combination_count += left_combination_count * right_combination
【在 s****a 的大作中提到】
: 我问面试官是推导出一个公式吗，他说用一个公式表示可能比较困难，他还让我写code
: 来计算看组成的binary tree树，提示我用递归。我想了半天也也没想出来怎么用递归
: 。哪位牛人可以指点一下吗？
|
m*****g
发帖数: 226 | 13 没看懂
讲讲
【在 d****i 的大作中提到】
: It is not hard :
: def T(n):
: if n == 0: return 1
: if n == 1: return 1
: sub_nodes_total = n - 1
: combination_count = 0
: for i in xrange(0, n): # i iterated from 0 to (n - 1)
: left_node_count = i
: right_node_count = sub_nodes_total - i
: left_combination_count = T(i) # combination count of left sub tree
|
w*****1
发帖数: 245 | 14 两个node为什么只能build 2个trees??
两个node都可以当root是吧，再加上左或右child。。。。4个吧？？ |
l*****a
发帖数: 14598 | 15 only 2 nodes
where did the other 2 came from？
【在 w*****1 的大作中提到】
: 两个node为什么只能build 2个trees??
: 两个node都可以当root是吧，再加上左或右child。。。。4个吧？？
|
t**g
发帖数: 1164 | 16 for 2 nodes A/B
do we differ between left tree and right tree?
i mean
A
/
B (B是left child)
or
A
\
B(B right child)
这算2个不同的tree么
【在 l*****a 的大作中提到】
: only 2 nodes
: where did the other 2 came from？
|
B*****t
发帖数: 335 | 17 I think the question is to ask "how many different BINARY SEARCH TREES", not
"binary trees", otherwise the answer is not Catalan number, but the answer
can also be found by DP.
one
【在 s****a 的大作中提到】
: 不知道是不是旧题，在版面上没搜到。
: how many different binary trees you can build with N nodes? For example, one
: node: 1 tree; 2 nodes: 2 trees; 3 nodes: 5 trees...
: 面试的时候没想起来怎么做时间就到了，很是郁闷。
|
l*****a
发帖数: 14598 | 18 they are definitely different
【在 t**g 的大作中提到】
: for 2 nodes A/B
: do we differ between left tree and right tree?
: i mean
: A
: /
: B (B是left child)
: or
: A
: \
: B(B right child)
|
l*****a
发帖数: 14598 | 19 no,they just ask how many binary trees
denali's answer is right
not
answer
【在 B*****t 的大作中提到】
: I think the question is to ask "how many different BINARY SEARCH TREES", not
: "binary trees", otherwise the answer is not Catalan number, but the answer
: can also be found by DP.
:
: one
|
z*****9
发帖数: 86 | |
a**********k
发帖数: 1953 | |
