logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
今天面的太惨了....
avatar
今天面的太惨了....# JobHunting - 待字闺中
w*x
1 楼
完全二叉树求节点要怎么求来着？
有什么优化？
avatar
j*y
2 楼
还真的让求完全二叉树的 node 个数阿 ?

【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
avatar
l*a
3 楼
上次不是有人问过吗

【在 j*****y 的大作中提到】
: 还真的让求完全二叉树的 node 个数阿 ?
avatar
l*a
4 楼
传说中的推特？

【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
avatar
w*x
5 楼

不是

【在 l*****a 的大作中提到】
: 传说中的推特？
avatar
w*x
6 楼

有啥很大不同不？？有比O(n)更好的？？

【在 l*****a 的大作中提到】
: 上次不是有人问过吗
avatar
f*e
7 楼
O(h^2)=O(logN^2)

【在 w****x 的大作中提到】
:
: 有啥很大不同不？？有比O(n)更好的？？
avatar
w*x
8 楼

具体？？？

【在 f*****e 的大作中提到】
: O(h^2)=O(logN^2)
avatar
d*x
9 楼
类似二分啊

【在 w****x 的大作中提到】
:
: 具体？？？
avatar
a*m
12 楼
啥叫求节点？数目？
１＋２＋４＋８＋１６＋。。。。　-> 2^n-1?

【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
avatar
p*p
13 楼
2^h - 1 is for perfect binary tree
complete bt might not be perfect

【在 a********m 的大作中提到】
: 啥叫求节点？数目？
: １＋２＋４＋８＋１６＋。。。。　-> 2^n-1?
avatar
a*m
14 楼
恩。你说滴堆。俺弄混了。complete这词太迷惑人了。

【在 p*****p 的大作中提到】
: 2^h - 1 is for perfect binary tree
: complete bt might not be perfect
avatar
G*A
15 楼
还是不明白题目.
是求一个完全二叉树的所有节点个数？还是求某个节电的index?还是别的？

【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
avatar
e*s
16 楼
==
O(h^2)=O(logN^2) 怎么看得怪怪的
h ^ 2 不应该是等于 n 吗？
avatar
c*t
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 吗？
avatar
G*A
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 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
avatar
e*s
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;
}
avatar
p*2
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
}
avatar
w*x
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
: }
:
avatar
l*a
23 楼
你C++ cow怎么不申请他们公司
有钱又有闲

【在 w****x 的大作中提到】
:
: 又在上班时间逛论坛
avatar
w*x
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
: }
:
avatar
a*o
25 楼
上面不是写过一个差不多的C++吗?

【在 w****x 的大作中提到】
:
: 这个解法太牛叉了，二爷是怎么想出来了，服了！
avatar
l*a
26 楼
他眼里只有2爷

【在 a***o 的大作中提到】
: 上面不是写过一个差不多的C++吗?
avatar
w*x
27 楼

不是，前面那个写的太长了，实在看不下去

【在 l*****a 的大作中提到】
: 他眼里只有2爷
avatar
a*o
28 楼
zan!

【在 l*****a 的大作中提到】
: 他眼里只有2爷
avatar
p*2
29 楼

恭喜大牛可以看scala code了。

【在 w****x 的大作中提到】
:
: 不是，前面那个写的太长了，实在看不下去
avatar
w*x
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;
}
avatar
T*s
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;
相关阅读
[合集] 告诉你！OPT 3个月没工作一点事都没有！问道G题(3)各位前辈，EPIC ON-SITE求经验。。同学们，找工作不要光看base， bonus也很重要G 家面试求祝福找几个headhunter比较好?你最大的优势是什么？提供 G 家内推OPT和H1B两问题咨询加州小公司面试问题这句话是表示至少要有绿卡吗？Authorized to work in the U.S on a permanent basis.求ASIC相关工作的referisilonH1b approval收到后，10/1生效前驾照更新问题on site临走时被告知还要见我一次,Google 这种公司会不会看人下菜碟？Dr. Dobb's 2012 Salary Surveyoracle offer有给signon bonus和rsu的么？刚才面了一Ａ３女码，没来得及打架 (转载)One FEA position
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。