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 的大作中提到】
: 可不可以这样，对于每个节点，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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 可不可以这样，对于每个节点，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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
:
: 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
|
