j*y
2 楼
还真的让求完全二叉树的 node 个数阿 ?
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
l*a
3 楼
上次不是有人问过吗
【在 j*****y 的大作中提到】
: 还真的让求完全二叉树的 node 个数阿 ?
【在 j*****y 的大作中提到】
: 还真的让求完全二叉树的 node 个数阿 ?
l*a
4 楼
传说中的推特？
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
w*x
5 楼
不是
【在 l*****a 的大作中提到】
: 传说中的推特？
w*x
6 楼
有啥很大不同不？？有比O(n)更好的？？
【在 l*****a 的大作中提到】
: 上次不是有人问过吗
f*e
7 楼
O(h^2)=O(logN^2)
【在 w****x 的大作中提到】
:
: 有啥很大不同不？？有比O(n)更好的？？
【在 w****x 的大作中提到】
:
: 有啥很大不同不？？有比O(n)更好的？？
w*x
8 楼
具体？？？
【在 f*****e 的大作中提到】
: O(h^2)=O(logN^2)
d*x
9 楼
类似二分啊
【在 w****x 的大作中提到】
:
: 具体？？？
【在 w****x 的大作中提到】
:
: 具体？？？
f*e
10 楼
http://www.mitbbs.com/article/JobHunting/32251211_3.html
有些细节省略了。
【在 w****x 的大作中提到】
:
: 具体？？？
有些细节省略了。
【在 w****x 的大作中提到】
:
: 具体？？？
s*0
11 楼
store in array
【在 f*****e 的大作中提到】
: http://www.mitbbs.com/article/JobHunting/32251211_3.html
: 有些细节省略了。
【在 f*****e 的大作中提到】
: http://www.mitbbs.com/article/JobHunting/32251211_3.html
: 有些细节省略了。
a*m
12 楼
啥叫求节点？数目？
１＋２＋４＋８＋１６＋。。。。 -> 2^n-1?
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
１＋２＋４＋８＋１６＋。。。。 -> 2^n-1?
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
p*p
13 楼
2^h - 1 is for perfect binary tree
complete bt might not be perfect
【在 a********m 的大作中提到】
: 啥叫求节点？数目？
: １＋２＋４＋８＋１６＋。。。。 -> 2^n-1?
complete bt might not be perfect
【在 a********m 的大作中提到】
: 啥叫求节点？数目？
: １＋２＋４＋８＋１６＋。。。。 -> 2^n-1?
a*m
14 楼
恩。你说滴堆。俺弄混了。complete这词太迷惑人了。
【在 p*****p 的大作中提到】
: 2^h - 1 is for perfect binary tree
: complete bt might not be perfect
【在 p*****p 的大作中提到】
: 2^h - 1 is for perfect binary tree
: complete bt might not be perfect
G*A
15 楼
还是不明白题目.
是求一个完全二叉树的所有节点个数？还是求某个节电的index?还是别的？
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
是求一个完全二叉树的所有节点个数？还是求某个节电的index?还是别的？
【在 w****x 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
e*s
16 楼
==
O(h^2)=O(logN^2) 怎么看得怪怪的
h ^ 2 不应该是等于 n 吗？
O(h^2)=O(logN^2) 怎么看得怪怪的
h ^ 2 不应该是等于 n 吗？
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 吗？
And also, for perfect bt, n= 2^(h+1)-1
【在 e***s 的大作中提到】
: ==
: O(h^2)=O(logN^2) 怎么看得怪怪的
: h ^ 2 不应该是等于 n 吗？
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 的大作中提到】
: 完全二叉树求节点要怎么求来着？
: 有什么优化？
/************/
这个行么？
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
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;
}
如果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
20 楼
这个不错，面试很难想到呀。一会儿练练
【在 f*****e 的大作中提到】
: http://www.mitbbs.com/article/JobHunting/32251211_3.html
: 有些细节省略了。
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
}
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
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
23 楼
你C++ cow怎么不申请他们公司
有钱又有闲
【在 w****x 的大作中提到】
:
: 又在上班时间逛论坛
有钱又有闲
【在 w****x 的大作中提到】
:
: 又在上班时间逛论坛
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
: }
:
a*o
25 楼
上面不是写过一个差不多的C++吗?
【在 w****x 的大作中提到】
:
: 这个解法太牛叉了，二爷是怎么想出来了，服了！
【在 w****x 的大作中提到】
:
: 这个解法太牛叉了，二爷是怎么想出来了，服了！
l*a
26 楼
他眼里只有2爷
【在 a***o 的大作中提到】
: 上面不是写过一个差不多的C++吗?
【在 a***o 的大作中提到】
: 上面不是写过一个差不多的C++吗?
w*x
27 楼
不是，前面那个写的太长了，实在看不下去
【在 l*****a 的大作中提到】
: 他眼里只有2爷
a*o
28 楼
zan!
【在 l*****a 的大作中提到】
: 他眼里只有2爷
【在 l*****a 的大作中提到】
: 他眼里只有2爷
p*2
29 楼
恭喜大牛可以看scala code了。
【在 w****x 的大作中提到】
:
: 不是，前面那个写的太长了，实在看不下去
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;
}
{
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
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;
【在 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;
相关阅读
on-site 一周了，还没消息，悲剧了?大家给我点建议吧 关于商讨offer最近在面试GE Healthcare 的最近微软某些部门是不是在涨工资？？ (转载)Power electronics engineer research positionfacebook google zynga microsoft twitter 在大家心目中排名如何面试google和microsoft应该做一些什么样的题？光学的，都在哪里找工呀求教过来人关于ＭＢＡ找工作都觉得现在形势好吗？如何补救 浪费的 OPT，转 H1B 太早了怎么这么悲剧跳槽离职，请问有什么程序？？生活费差别一个经典的随机数的问题。求教。攒个rp吧，发个groupon面经请问前段时间说可以帮忙推荐google工作的帖子在哪啊？帮lg问一下 签offer前有什么问题问HR网络公司面经，求祝福金融公司的online test是选Java还是选C好？