j*y
3 楼
类似于这个的?
/\
/\
【在 c********t 的大作中提到】
: 问如何求一个complete binary tree的nodes个数？
/\
/\
【在 c********t 的大作中提到】
: 问如何求一个complete binary tree的nodes个数？
c*k
4 楼
我日
c*t
5 楼
是的
【在 j*****y 的大作中提到】
: 类似于这个的?
: /\
: /\
【在 j*****y 的大作中提到】
: 类似于这个的?
: /\
: /\
b*a
6 楼
lol, 造福人类
l*a
7 楼
1+2^1+2^2+2^3...
【在 c********t 的大作中提到】
: 是的
【在 c********t 的大作中提到】
: 是的
j*y
8 楼
那总要给出一些条件吧， 比如 叶子的个数
如果 leaf number is N
那么非 leaf nodes number is N-1
total is 2N -1
【在 c********t 的大作中提到】
: 是的
如果 leaf number is N
那么非 leaf nodes number is N-1
total is 2N -1
【在 c********t 的大作中提到】
: 是的
c*t
9 楼
你这个是full binary tree吧
complete要求是尽量full,但最后一层可以不满，但必须都靠左
A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as
possible
这是一道编程题。
【在 l*****a 的大作中提到】
: 1+2^1+2^2+2^3...
complete要求是尽量full,但最后一层可以不满，但必须都靠左
A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as
possible
这是一道编程题。
【在 l*****a 的大作中提到】
: 1+2^1+2^2+2^3...
l*a
10 楼
那你说能有固定结果吗？
【在 c********t 的大作中提到】
: 你这个是full binary tree吧
: complete要求是尽量full,但最后一层可以不满，但必须都靠左
: A complete binary tree is a binary tree in which every level, except
: possibly the last, is completely filled, and all nodes are as far left as
: possible
: 这是一道编程题。
【在 c********t 的大作中提到】
: 你这个是full binary tree吧
: complete要求是尽量full,但最后一层可以不满，但必须都靠左
: A complete binary tree is a binary tree in which every level, except
: possibly the last, is completely filled, and all nodes are as far left as
: possible
: 这是一道编程题。
c*t
11 楼
没有固定结果啊，这是一道编程题，输入是一个complete binary tree,要求返回nodes
个数，遍历是一种方法，但是要O（n)，也没有用上complete 的特性。
【在 l*****a 的大作中提到】
: 那你说能有固定结果吗？
个数，遍历是一种方法，但是要O（n)，也没有用上complete 的特性。
【在 l*****a 的大作中提到】
: 那你说能有固定结果吗？
f*e
12 楼
这题不是讨论过吗？用二分查找，O(h^2)，h是高度。
http://mitbbs.com/article1/JobHunting/32251211_3_0.html
nodes
【在 c********t 的大作中提到】
: 没有固定结果啊，这是一道编程题，输入是一个complete binary tree,要求返回nodes
: 个数，遍历是一种方法，但是要O（n)，也没有用上complete 的特性。
http://mitbbs.com/article1/JobHunting/32251211_3_0.html
nodes
【在 c********t 的大作中提到】
: 没有固定结果啊，这是一道编程题，输入是一个complete binary tree,要求返回nodes
: 个数，遍历是一种方法，但是要O（n)，也没有用上complete 的特性。
c*t
13 楼
多谢！
但是这个只能找到拐点(最后一行最后的叶子）啊，没计算nodes个数啊？还有为什么是
h^2, 不是每一层都选择了either left or right for q, 应该是 O（h)啊？
【在 f*****e 的大作中提到】
: 这题不是讨论过吗？用二分查找，O(h^2)，h是高度。
: http://mitbbs.com/article1/JobHunting/32251211_3_0.html
:
: nodes
但是这个只能找到拐点(最后一行最后的叶子）啊，没计算nodes个数啊？还有为什么是
h^2, 不是每一层都选择了either left or right for q, 应该是 O（h)啊？
【在 f*****e 的大作中提到】
: 这题不是讨论过吗？用二分查找，O(h^2)，h是高度。
: http://mitbbs.com/article1/JobHunting/32251211_3_0.html
:
: nodes
j*y
14 楼
写了一个code
bool isLeftOneMoreLayer(TreeNode * root, int layer, int & moreNodes)
{
if(!root->right && layer == 1 )
{
return false;
}
if(root->right && layer == 1)
{
moreNodes += 2;
return true;
}
if(!isLeftOneMoreLayer(root->left, layer - 1, moreNodes))
{
return false;
}
if(!isLeftOneMoreLayer(root->right, layer - 1, moreNodes))
{
return false;
}
return true;
}
int numberOfNodesInCompleteTree(TreeNode * root)
{
int number = 0;
TreeNode * tmp = root;
int nodesOnALevel = 1;
int rightLayer = 0;
while(tmp)
{
++rightLayer;
number += nodesOnALevel;
nodesOnALevel * = 2;
tmp = tmp->right;
}
number += nodesOnALevel;
int moreNodes = 0;
isLeftOneMoreLayer(root, rightLayer, moreNodes);
return moreNodes + number;
}
nodes
【在 c********t 的大作中提到】
: 没有固定结果啊，这是一道编程题，输入是一个complete binary tree,要求返回nodes
: 个数，遍历是一种方法，但是要O（n)，也没有用上complete 的特性。
bool isLeftOneMoreLayer(TreeNode * root, int layer, int & moreNodes)
{
if(!root->right && layer == 1 )
{
return false;
}
if(root->right && layer == 1)
{
moreNodes += 2;
return true;
}
if(!isLeftOneMoreLayer(root->left, layer - 1, moreNodes))
{
return false;
}
if(!isLeftOneMoreLayer(root->right, layer - 1, moreNodes))
{
return false;
}
return true;
}
int numberOfNodesInCompleteTree(TreeNode * root)
{
int number = 0;
TreeNode * tmp = root;
int nodesOnALevel = 1;
int rightLayer = 0;
while(tmp)
{
++rightLayer;
number += nodesOnALevel;
nodesOnALevel * = 2;
tmp = tmp->right;
}
number += nodesOnALevel;
int moreNodes = 0;
isLeftOneMoreLayer(root, rightLayer, moreNodes);
return moreNodes + number;
}
nodes
【在 c********t 的大作中提到】
: 没有固定结果啊，这是一道编程题，输入是一个complete binary tree,要求返回nodes
: 个数，遍历是一种方法，但是要O（n)，也没有用上complete 的特性。
c*t
15 楼
if(!root->right && layer == 1 )
{
return false;
}
好像有问题。
下面这个也是complete的
1
/
2
还有你的复杂度是 2^n？
【在 j*****y 的大作中提到】
: 写了一个code
: bool isLeftOneMoreLayer(TreeNode * root, int layer, int & moreNodes)
: {
: if(!root->right && layer == 1 )
: {
: return false;
: }
: if(root->right && layer == 1)
: {
: moreNodes += 2;
{
return false;
}
好像有问题。
下面这个也是complete的
1
/
2
还有你的复杂度是 2^n？
【在 j*****y 的大作中提到】
: 写了一个code
: bool isLeftOneMoreLayer(TreeNode * root, int layer, int & moreNodes)
: {
: if(!root->right && layer == 1 )
: {
: return false;
: }
: if(root->right && layer == 1)
: {
: moreNodes += 2;
j*y
16 楼
对的，我没用 binary search.
需要改进
我觉得这个题目应该要 guarrantee 是 complete的，还需要check 是不是 complete的？
那太复杂了。
【在 c********t 的大作中提到】
: if(!root->right && layer == 1 )
: {
: return false;
: }
: 好像有问题。
: 下面这个也是complete的
: 1
: /
: 2
: 还有你的复杂度是 2^n？
需要改进
我觉得这个题目应该要 guarrantee 是 complete的，还需要check 是不是 complete的？
那太复杂了。
【在 c********t 的大作中提到】
: if(!root->right && layer == 1 )
: {
: return false;
: }
: 好像有问题。
: 下面这个也是complete的
: 1
: /
: 2
: 还有你的复杂度是 2^n？
j*y
17 楼
复杂度是 n, 每个点最坏情况下会走一遍。
【在 c********t 的大作中提到】
: if(!root->right && layer == 1 )
: {
: return false;
: }
: 好像有问题。
: 下面这个也是complete的
: 1
: /
: 2
: 还有你的复杂度是 2^n？
【在 c********t 的大作中提到】
: if(!root->right && layer == 1 )
: {
: return false;
: }
: 好像有问题。
: 下面这个也是complete的
: 1
: /
: 2
: 还有你的复杂度是 2^n？
c*t
18 楼
对，是O（n)
input肯定是complete的，不过我的意思是你对complete理解有问题,以下这个也是
complete bt.
1
/ \
2 3
/
4
的？
【在 j*****y 的大作中提到】
: 对的，我没用 binary search.
: 需要改进
: 我觉得这个题目应该要 guarrantee 是 complete的，还需要check 是不是 complete的？
: 那太复杂了。
input肯定是complete的，不过我的意思是你对complete理解有问题,以下这个也是
complete bt.
1
/ \
2 3
/
4
的？
【在 j*****y 的大作中提到】
: 对的，我没用 binary search.
: 需要改进
: 我觉得这个题目应该要 guarrantee 是 complete的，还需要check 是不是 complete的？
: 那太复杂了。
j*y
19 楼
你的理解是对的，我的理解是错的，
就像 binary heap 中的 complete binary tree 一样。
thanks .
【在 c********t 的大作中提到】
: 对，是O（n)
: input肯定是complete的，不过我的意思是你对complete理解有问题,以下这个也是
: complete bt.
: 1
: / \
: 2 3
: /
: 4
:
: 的？
就像 binary heap 中的 complete binary tree 一样。
thanks .
【在 c********t 的大作中提到】
: 对，是O（n)
: input肯定是complete的，不过我的意思是你对complete理解有问题,以下这个也是
: complete bt.
: 1
: / \
: 2 3
: /
: 4
:
: 的？
c*t
20 楼
不客气
感觉只要把你的codes里前几行
if(!root->right && layer == 1 )
{
return false;
}
加上if(root->left) nodenumber+=1就可以。
看看有没有高人给 binary的解法吧。
【在 j*****y 的大作中提到】
: 你的理解是对的，我的理解是错的，
: 就像 binary heap 中的 complete binary tree 一样。
: thanks .
感觉只要把你的codes里前几行
if(!root->right && layer == 1 )
{
return false;
}
加上if(root->left) nodenumber+=1就可以。
看看有没有高人给 binary的解法吧。
【在 j*****y 的大作中提到】
: 你的理解是对的，我的理解是错的，
: 就像 binary heap 中的 complete binary tree 一样。
: thanks .
j*y
21 楼
binary的解法就是一些数学逻辑难得搞清楚。
【在 c********t 的大作中提到】
: 不客气
: 感觉只要把你的codes里前几行
: if(!root->right && layer == 1 )
: {
: return false;
: }
: 加上if(root->left) nodenumber+=1就可以。
: 看看有没有高人给 binary的解法吧。
【在 c********t 的大作中提到】
: 不客气
: 感觉只要把你的codes里前几行
: if(!root->right && layer == 1 )
: {
: return false;
: }
: 加上if(root->left) nodenumber+=1就可以。
: 看看有没有高人给 binary的解法吧。
c*t
22 楼
木人回了，自己顶顶
【在 j*****y 的大作中提到】
: binary的解法就是一些数学逻辑难得搞清楚。
【在 j*****y 的大作中提到】
: binary的解法就是一些数学逻辑难得搞清楚。
d*g
23 楼
他这个算法应该是O(h^2)。第一次迭代算出根节点的左子树是不是满的，如果是满的就
往右走，否则往左走。在查看左子树的时候最多遍历h个节点一次，就是O(h)。总复杂
度就
是O(h^2)。
计算节点个数我想是不是可以这样算：首先假设树是满的。第一次迭代的时候如果往左
走，说明左子树不是满的，那么右子树一定少一层，于是就减去右子树的所有叶子的个
数。这样每一层下来如果往左走，都减去右子树的所有叶节点的个数。等大循环结束的
时候，也就算出了总节点个数。比如：
1
2 3
4 5 6 7
8 9 10
这样一个树，先假设节点数是15个。然后第一次循环往左走，到2处，那么1的右子树一
定少一层，容易计算出这时右子树的叶子个数是4，于是15-4=11。第二次循环往右走，
到5处，节点总数不做变动。最后一次循环只用查看5有几个叶节点就可以了。
【在 c********t 的大作中提到】
: 多谢！
: 但是这个只能找到拐点(最后一行最后的叶子）啊，没计算nodes个数啊？还有为什么是
: h^2, 不是每一层都选择了either left or right for q, 应该是 O（h)啊？
j*y
24 楼
int numberNodes(TreeNode * root)
{
int result = 0;
int nodes = 1;
TreeNode *tmp = root;
int rightLayer = 0;
while(tmp)
{
result += nodes;
++rightLayer;
nodes *= 2;
tmp = tmp->right;
}
int leftLayer = 0;
tmp = root;
while(tmp)
{
++leftLayer;
tmp = tmp->left;
}
if(leftLayer == rightLayer)
{
return result;
}
tmp = root;
while(tmp)
{
--rightLayer;
int layer = 0;
TreeNode * cur_tmp = tmp->left;
while(cur_tmp)
{
++layer;
cur_tmp = cur_tmp->right;
}
if(layer == right_layer)
{
nodes = nodes / 2;
tmp = tmp->left;
}
else
{
nodes = nodes / 2;
result += nodes;
tmp = tmp->right;
}
}
return result;
}
binary的解法就是一些数学逻辑难得搞清楚。
【在 j*****y 的大作中提到】
: binary的解法就是一些数学逻辑难得搞清楚。
{
int result = 0;
int nodes = 1;
TreeNode *tmp = root;
int rightLayer = 0;
while(tmp)
{
result += nodes;
++rightLayer;
nodes *= 2;
tmp = tmp->right;
}
int leftLayer = 0;
tmp = root;
while(tmp)
{
++leftLayer;
tmp = tmp->left;
}
if(leftLayer == rightLayer)
{
return result;
}
tmp = root;
while(tmp)
{
--rightLayer;
int layer = 0;
TreeNode * cur_tmp = tmp->left;
while(cur_tmp)
{
++layer;
cur_tmp = cur_tmp->right;
}
if(layer == right_layer)
{
nodes = nodes / 2;
tmp = tmp->left;
}
else
{
nodes = nodes / 2;
result += nodes;
tmp = tmp->right;
}
}
return result;
}
binary的解法就是一些数学逻辑难得搞清楚。
【在 j*****y 的大作中提到】
: binary的解法就是一些数学逻辑难得搞清楚。
e*e
25 楼
知道拐点的位置就可以算出来节点个数吧！
a*o
26 楼
好像这个例子会有bug?
o
o o
o o o o
o o o
最后一行最后面那个node会少算?
【在 j*****y 的大作中提到】
: int numberNodes(TreeNode * root)
: {
: int result = 0;
: int nodes = 1;
: TreeNode *tmp = root;
: int rightLayer = 0;
: while(tmp)
: {
: result += nodes;
: ++rightLayer;
o
o o
o o o o
o o o
最后一行最后面那个node会少算?
【在 j*****y 的大作中提到】
: int numberNodes(TreeNode * root)
: {
: int result = 0;
: int nodes = 1;
: TreeNode *tmp = root;
: int rightLayer = 0;
: while(tmp)
: {
: result += nodes;
: ++rightLayer;
j*y
27 楼
thanks.
改了一下，要不再给看看 :)
【在 a***o 的大作中提到】
: 好像这个例子会有bug?
: o
: o o
: o o o o
: o o o
: 最后一行最后面那个node会少算?
改了一下，要不再给看看 :)
【在 a***o 的大作中提到】
: 好像这个例子会有bug?
: o
: o o
: o o o o
: o o o
: 最后一行最后面那个node会少算?
e*o
28 楼
int Nnodes(TreeNode *root) {
if ( root == NULL )
return 0;
if ( root->left == NULL )
return 1;
TreeNode *ptr(root);
int height(0);
while ( ptr ) {
++height;
ptr = ptr->left;
}
ptr = root->left;
int hTemp(0);
while ( ptr ) {
++hTemp;
ptr = ptr->right;
}
if ( hTemp == height-1 )
return ( 1 << hTemp ) + Nnodes(root->right);
else
return ( 1 << hTemp ) + Nnodes(root->left);
}
测试了一下好像没问题。 O(h^2)
if ( root == NULL )
return 0;
if ( root->left == NULL )
return 1;
TreeNode *ptr(root);
int height(0);
while ( ptr ) {
++height;
ptr = ptr->left;
}
ptr = root->left;
int hTemp(0);
while ( ptr ) {
++hTemp;
ptr = ptr->right;
}
if ( hTemp == height-1 )
return ( 1 << hTemp ) + Nnodes(root->right);
else
return ( 1 << hTemp ) + Nnodes(root->left);
}
测试了一下好像没问题。 O(h^2)
a*o
29 楼
zan,这个不错
【在 e******o 的大作中提到】
: int Nnodes(TreeNode *root) {
: if ( root == NULL )
: return 0;
: if ( root->left == NULL )
: return 1;
: TreeNode *ptr(root);
: int height(0);
: while ( ptr ) {
: ++height;
: ptr = ptr->left;
【在 e******o 的大作中提到】
: int Nnodes(TreeNode *root) {
: if ( root == NULL )
: return 0;
: if ( root->left == NULL )
: return 1;
: TreeNode *ptr(root);
: int height(0);
: while ( ptr ) {
: ++height;
: ptr = ptr->left;
相关阅读
【多字长漫画】 瞅了眼妹子屁股之后咋解释给娇客们拜年了到现在还支持中医中药的人，我来给你们定性网盘云公司做raid吗买房子和绿卡（不好意思，考古没有结果） (转载)中医无用没法解释真心问大家一个问题，都别人身攻击， 老老实实回答 (转载)中国现世界首例人类与恐龙共存证据震惊世界 (转载)Re: 再一次被苹果给狠狠的感动了 (转载)全裸春晚想法不错，就一个问题没法解决木头是怎么加工的Staples奇遇记 (转载)健康无公害笑话20-zz学术一下，开网盘的公司机房Google 还是给面子了喝母乳养成的毛病白怪约翰身上的纹身出国的男的一般都是变态 这里面是有原因的 (转载)巴马在印度种的树快要死了 (转载)据说生病的动物会自己找草药吃