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;
相关阅读
碉堡了! 体操姐给大卡车撞倒後在车轮底下翻滚成功逃过一劫追尾宝马5系，对方张口要8W，我叫来20多个兄弟firefox 24.0 is availableRe: 宋祖英德语歌唱的得还凑合 (转载)表演时给手机铃声骚扰, 不但没有生气, 还幽默地来一段即兴啊!听说新红楼梦是插图版世界第一贱人！我认识一个生物男 (转载)为啥用脚踩的葡萄制作的酒味道好?Re: 最近投稿，意外被拒，很气愤，无奈无语啊。大家说说 (转载)Re: 今天去买冰酒，三大酒庄的200毫升都缺货 (转载)妹的，礼节性上床了 (转载)感谢xiaopo几个笑话 -- 依然记得那年英国科学家绘制41个国家“国民脸” (转载)[問卦] 英文真的重要嗎?Re: 最近投稿，意外被拒，很气愤，无奈无语啊。大家说说 (转载)感觉学中文的白女比学中文的白男找中国人的比例要小做一个真诚的人，然后，无所畏惧毛少将原来是周总理和黄永胜搞出的项目 (转载)