w****x 发帖数: 2483 | |
j*****y 发帖数: 1071 | 2 还真的让求完全二叉树的 node 个数阿 ?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 完全二叉树求节点要怎么求来着? : 有什么优化?
|
l*****a 发帖数: 14598 | 3 上次不是有人问过吗
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还真的让求完全二叉树的 node 个数阿 ?
|
l*****a 发帖数: 14598 | 4 传说中的推特?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 完全二叉树求节点要怎么求来着? : 有什么优化?
|
w****x 发帖数: 2483 | 5
不是
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 传说中的推特?
|
w****x 发帖数: 2483 | 6
有啥很大不同不??有比O(n)更好的??
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上次不是有人问过吗
|
f*****e 发帖数: 2992 | 7 O(h^2)=O(logN^2)
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 有啥很大不同不??有比O(n)更好的??
|
w****x 发帖数: 2483 | 8
具体???
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(h^2)=O(logN^2)
|
d**********x 发帖数: 4083 | 9 类似二分啊
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 具体???
|
f*****e 发帖数: 2992 | |
|
|
s****0 发帖数: 117 | |
a********m 发帖数: 15480 | 12 啥叫求节点?数目?
1+2+4+8+16+。。。。 -> 2^n-1?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 完全二叉树求节点要怎么求来着? : 有什么优化?
|
p*****p 发帖数: 379 | 13 2^h - 1 is for perfect binary tree
complete bt might not be perfect
【在 a********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 啥叫求节点?数目? : 1+2+4+8+16+。。。。 -> 2^n-1?
|
a********m 发帖数: 15480 | 14 恩。你说滴堆。俺弄混了。complete这词太迷惑人了。
【在 p*****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2^h - 1 is for perfect binary tree : complete bt might not be perfect
|
G****A 发帖数: 4160 | 15 还是不明白题目.
是求一个完全二叉树的所有节点个数?还是求某个节电的index?还是别的?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 完全二叉树求节点要怎么求来着? : 有什么优化?
|
e***s 发帖数: 799 | 16 ==
O(h^2)=O(logN^2) 怎么看得怪怪的
h ^ 2 不应该是等于 n 吗? |
c********t 发帖数: 5706 | 17 for complete BT or perfect BT, height=log(n);
And also, for perfect bt, n= 2^(h+1)-1
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : == : O(h^2)=O(logN^2) 怎么看得怪怪的 : h ^ 2 不应该是等于 n 吗?
|
G****A 发帖数: 4160 | 18 update:修改了一下
/************/
这个行么?
int NumOfNodes(Node* p, int max_depth, int cur_depth, int index)
{
if (max_depth <= 1)
return max_depth;
if (!p)
return 0;
if (cur_depth == max_depth-1 && !p->left)
return 2 * index - 1;
if (cur_depth == max_depth-1 && !p->right)
return 2 * index;
int L = NumOfNodes(p->left, max_depth, cur_depth+1, index*2);
return L ? L : NumOfNodes(p->right, max_depth, cur_depth+1, index*2+1);
}
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 完全二叉树求节点要怎么求来着? : 有什么优化?
|
e***s 发帖数: 799 | 19 刚写的,思想是,node的总数等于left subtree + right subtree + 1;
如果left subtree perfect 直接算 2^h -1; 如果不,递归进去
同理right subtree
public static int nodesInCompleteBT(TreeNode root){
if(root == null)
return 0;
if(root.left == null) // one node tree
return 1;
int height = 1;
TreeNode node = root.left;
while(node != null)
{
node = node.left;
height++;
}
return nodesInCompleteBTHelper(root, height);
}
public static int nodesInCompleteBTHelper(TreeNode root, int h){
if(root == null)
return 0;
if(root.left == null)
return 1;
int L = 0, R = 0;
int count = 1;
TreeNode node = root.left;
while(node != null)
{
node = node.right;
count++;
}
if(count == h)
L = (int)Math.pow(2, h -1) - 1;
else
L = nodesInCompleteBTHelper(root.left, h - 1);
count = 1;
node = root.right;
while(node != null)
{
node = node.right;
count++;
}
if(count == h)
R = (int)Math.pow(2, h - 1) - 1;
else
R = nodesInCompleteBTHelper(root.right, h - 1);
return L + R + 1;
} |
p*****2 发帖数: 21240 | |
|
|
p*****2 发帖数: 21240 | 21 def getLeftHeight(root:Option[TreeNode]):Int={
var h=0
var node=root
while(!node.isEmpty){
h+=1
node=node.get.left
}
h
}
def getRightHeight(root:Option[TreeNode]):Int={
var h=0
var node=root
while(!node.isEmpty){
h+=1
node=node.get.right
}
h
}
def getNodesNum(h:Int):Int={
return math.pow(2,h).toInt-1
}
def totalNodes(root:Option[TreeNode]):Int={
var h=getLeftHeight(root)
var node=root
var total=0
while(h>0 && !node.isEmpty){
if (getRightHeight(node.get.left)==h-1){
total+=getNodesNum(h-1)+1
node=node.get.right
}
else{
total+=getNodesNum(h-2)+1
node=node.get.left
}
h-=1
}
total
}
|
w****x 发帖数: 2483 | 22
又在上班时间逛论坛
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : def getLeftHeight(root:Option[TreeNode]):Int={ : var h=0 : var node=root : while(!node.isEmpty){ : h+=1 : node=node.get.left : } : h : } :
|
l*****a 发帖数: 14598 | 23 你C++ cow怎么不申请他们公司
有钱又有闲
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 又在上班时间逛论坛
|
w****x 发帖数: 2483 | 24
这个解法太牛叉了,二爷是怎么想出来了,服了!
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : def getLeftHeight(root:Option[TreeNode]):Int={ : var h=0 : var node=root : while(!node.isEmpty){ : h+=1 : node=node.get.left : } : h : } :
|
a***o 发帖数: 1182 | 25 上面不是写过一个差不多的C++吗?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这个解法太牛叉了,二爷是怎么想出来了,服了!
|
l*****a 发帖数: 14598 | 26 他眼里只有2爷
【在 a***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上面不是写过一个差不多的C++吗?
|
w****x 发帖数: 2483 | 27
不是,前面那个写的太长了,实在看不下去
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他眼里只有2爷
|
a***o 发帖数: 1182 | 28 zan!
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他眼里只有2爷
|
p*****2 发帖数: 21240 | 29
恭喜大牛可以看scala code了。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不是,前面那个写的太长了,实在看不下去
|
w****x 发帖数: 2483 | 30 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
int getHeight(NODE* pNode, bool bLft)
{
int nRet = 0;
NODE* pIter = pNode;
while (NULL != pIter)
{
if (bLft)
pIter = pIter->pLft;
else
pIter = pIter->pRgt;
nRet++;
}
return nRet;
}
int getNum(int h)
{
return pow((double)2, h) -1;
}
int getNumberOfNodes(NODE* pRoot)
{
NODE* pNode = pRoot;
int h = getHeight(pNode, true);
int nRet = 0;
while (NULL != pNode)
{
int nTmp = getHeight(pNode->pLft, false);
if (nTmp == h - 1)
{
nRet += 1 + getNum(h-1);
pNode = pNode->pRgt;
}
else
{
nRet += 1 + getNum(h-2);
pNode = pNode->pLft;
}
h--;
}
return nRet;
} |
|
|
T*********s 发帖数: 17839 | 31 人活早干完了
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : struct NODE : { : int nVal; : NODE* pLft; : NODE* pRgt; : NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {} : }; : int getHeight(NODE* pNode, bool bLft) : { : int nRet = 0;
|