EPI 题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

EPI 题目

EPI 题目# JobHunting - 待字闺中

m*42014-01-14 08:01

1 楼

Write a function that returns the size of the largest subtree that is
complete.
请问怎么解啊

b*a2014-01-14 08:01

2 楼

I think you can always mail the authors about the questions you had.

T*e2014-01-14 08:01

3 楼

可不可以这样，对于每个节点，NULL就返回0，如果其左子树和右子树返回的数目相等
，就说明到这个节点为止的树是满的（但这并不说明这个节点以下所有树都是满的，只
说明起码该节点加上其左右子树是满树），就返回左子树+右子树+1，否则就返回1，代
表自己的节点。
然后每次recursive都带一个引用的max存全局的最大值

w*s2014-01-14 08:01

4 楼

EPI的题书上不是有答案吗

【在 T******e 的大作中提到】

: 可不可以这样，对于每个节点，NULL就返回0，如果其左子树和右子树返回的数目相等
: ，就说明到这个节点为止的树是满的（但这并不说明这个节点以下所有树都是满的，只
: 说明起码该节点加上其左右子树是满树），就返回左子树+右子树+1，否则就返回1，代
: 表自己的节点。
: 然后每次recursive都带一个引用的max存全局的最大值

w*t2014-01-14 08:01

5 楼

similar with this:
http://leetcode.com/2010/11/largest-binary-search-tree-bst-in.h

【在 m*******4 的大作中提到】

: Write a function that returns the size of the largest subtree that is
: complete.
: 请问怎么解啊

m*42014-01-14 08:01

6 楼

This is an extension problem. No answer

【在 w*******s 的大作中提到】

: EPI的题书上不是有答案吗

b*a2014-01-14 08:01

7 楼

I think your idea is correct with a tiny bug; what your algorithm is
returning the largest perfect binary tree instead of the largest complete
binary tree. With your algorithm, this problem can be solved in O(n) time I
think.

【在 T******e 的大作中提到】

b*e2014-01-14 08:01

8 楼

Assume we know the height of each node, which can be computed on the fly
with O(n). Then it's just an extensive case study on the 3 possible status
of a subroot: incomplete, complete (but not perfect), perfect.
if (!tree.left is not complete) {
tree is not complete
} else {
if (tree.left is not perfect) {
tree is not complete
} else {
if (tree.right is not complete) {
tree is not complete
} else {
if (tree.right is not perfect) {
if (tree.left.height == tree.right.height) {
tree is complete but not perfect
} else {
tree is not complete
}
} else {
if (tree.left.height == tree.right.height) {
tree is perfect
} else {
tree is not complete
}
}
}
}
}

【在 m*******4 的大作中提到】

: Write a function that returns the size of the largest subtree that is
: complete.
: 请问怎么解啊

l*62014-01-14 08:01

9 楼

status
if (tree.left is not perfect) {
The tree can be complete if tree.left is not perfect
that is tree.left is complete tree.right is perfect tree.left.height - tree
.right.height = 1

【在 b***e 的大作中提到】

: Assume we know the height of each node, which can be computed on the fly
: with O(n). Then it's just an extensive case study on the 3 possible status
: of a subroot: incomplete, complete (but not perfect), perfect.
: if (!tree.left is not complete) {
: tree is not complete
: } else {
: if (tree.left is not perfect) {
: tree is not complete
: } else {
: if (tree.right is not complete) {

b*e2014-01-14 08:01

10 楼

That's right, made up. Thanks.

tree

【在 l******6 的大作中提到】

:
: status
: if (tree.left is not perfect) {
: The tree can be complete if tree.left is not perfect
: that is tree.left is complete tree.right is perfect tree.left.height - tree
: .right.height = 1