m*******4 发帖数: 34 | 1 Write a function that returns the size of the largest subtree that is
complete.
请问怎么解啊 |
b*****a 发帖数: 70 | 2 I think you can always mail the authors about the questions you had. |
T******e 发帖数: 157 | 3 可不可以这样,对于每个节点,NULL就返回0,如果其左子树和右子树返回的数目相等
,就说明到这个节点为止的树是满的(但这并不说明这个节点以下所有树都是满的,只
说明起码该节点加上其左右子树是满树),就返回左子树+右子树+1,否则就返回1,代
表自己的节点。
然后每次recursive都带一个引用的max存全局的最大值 |
w*******s 发帖数: 138 | 4 EPI的题书上不是有答案吗
【在 T******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可不可以这样,对于每个节点,NULL就返回0,如果其左子树和右子树返回的数目相等 : ,就说明到这个节点为止的树是满的(但这并不说明这个节点以下所有树都是满的,只 : 说明起码该节点加上其左右子树是满树),就返回左子树+右子树+1,否则就返回1,代 : 表自己的节点。 : 然后每次recursive都带一个引用的max存全局的最大值
|
w*****t 发帖数: 485 | 5 similar with this:
http://leetcode.com/2010/11/largest-binary-search-tree-bst-in.h
【在 m*******4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Write a function that returns the size of the largest subtree that is : complete. : 请问怎么解啊
|
m*******4 发帖数: 34 | 6
This is an extension problem. No answer
【在 w*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : EPI的题书上不是有答案吗
|
b*****a 发帖数: 70 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可不可以这样,对于每个节点,NULL就返回0,如果其左子树和右子树返回的数目相等 : ,就说明到这个节点为止的树是满的(但这并不说明这个节点以下所有树都是满的,只 : 说明起码该节点加上其左右子树是满树),就返回左子树+右子树+1,否则就返回1,代 : 表自己的节点。 : 然后每次recursive都带一个引用的max存全局的最大值
|
b***e 发帖数: 1419 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Write a function that returns the size of the largest subtree that is : complete. : 请问怎么解啊
|
l******6 发帖数: 340 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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***e 发帖数: 1419 | 10 That's right, made up. Thanks.
tree
【在 l******6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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
|