w****x
发帖数: 2483 | |
j*****y
发帖数: 1071 | 2 还真的让求完全二叉树的 node 个数阿 ?
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
|
l*****a
发帖数: 14598 | 3 上次不是有人问过吗
【在 j*****y 的大作中提到】
: 还真的让求完全二叉树的 node 个数阿 ?
|
l*****a
发帖数: 14598 | 4 传说中的推特？
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
|
w****x
发帖数: 2483 | 5
不是
【在 l*****a 的大作中提到】
: 传说中的推特？
|
w****x
发帖数: 2483 | 6
有啥很大不同不？？有比O(n)更好的？？
【在 l*****a 的大作中提到】
: 上次不是有人问过吗
|
f*****e
发帖数: 2992 | 7 O(h^2)=O(logN^2)
【在 w****x 的大作中提到】
:
: 有啥很大不同不？？有比O(n)更好的？？
|
w****x
发帖数: 2483 | 8
具体？？？
【在 f*****e 的大作中提到】
: O(h^2)=O(logN^2)
|
d**********x
发帖数: 4083 | 9 类似二分啊
【在 w****x 的大作中提到】
:
: 具体？？？
|
f*****e
发帖数: 2992 | |
|
|
s****0
发帖数: 117 | |
a********m
发帖数: 15480 | 12 啥叫求节点？数目？
１＋２＋４＋８＋１６＋。。。。 -> 2^n-1?
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
|
p*****p
发帖数: 379 | 13 2^h - 1 is for perfect binary tree
complete bt might not be perfect
【在 a********m 的大作中提到】
: 啥叫求节点？数目？
: １＋２＋４＋８＋１６＋。。。。 -> 2^n-1?
|
a********m
发帖数: 15480 | 14 恩。你说滴堆。俺弄混了。complete这词太迷惑人了。
【在 p*****p 的大作中提到】
: 2^h - 1 is for perfect binary tree
: complete bt might not be perfect
|
G****A
发帖数: 4160 | 15 还是不明白题目.
是求一个完全二叉树的所有节点个数？还是求某个节电的index?还是别的？
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
|
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 的大作中提到】
: ==
: 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 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
|
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 的大作中提到】
: 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 的大作中提到】
:
: 又在上班时间逛论坛
|
w****x
发帖数: 2483 | 24
这个解法太牛叉了，二爷是怎么想出来了，服了！
【在 p*****2 的大作中提到】
: 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 的大作中提到】
:
: 这个解法太牛叉了，二爷是怎么想出来了，服了！
|
l*****a
发帖数: 14598 | 26 他眼里只有2爷
【在 a***o 的大作中提到】
: 上面不是写过一个差不多的C++吗?
|
w****x
发帖数: 2483 | 27
不是，前面那个写的太长了，实在看不下去
【在 l*****a 的大作中提到】
: 他眼里只有2爷
|
a***o
发帖数: 1182 | 28 zan!
【在 l*****a 的大作中提到】
: 他眼里只有2爷
|
p*****2
发帖数: 21240 | 29
恭喜大牛可以看scala code了。
【在 w****x 的大作中提到】
:
: 不是，前面那个写的太长了，实在看不下去
|
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 的大作中提到】
: 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;
|
