K******g
发帖数: 1870 | 1 如果有人问你 Height of a BInary tree.
请问怎么回答？ |
j***n
发帖数: 301 | 2 遍历？
【在 K******g 的大作中提到】
: 如果有人问你 Height of a BInary tree.
: 请问怎么回答？
|
b*******y
发帖数: 239 | 3 如果他是笼统的问题，那 average和best case都差不多是log（N）吧，worst case是N
,所有子node全挂在一边了， 这个是用来测试你对tree是不是了解基础知识吧。
如果题目是很specific的一个tree的话，那我觉得也是遍历了。
等高手 |
r****o
发帖数: 1950 | 4 找二叉树的高度不是O(n)吗？
是N
【在 b*******y 的大作中提到】
: 如果他是笼统的问题，那 average和best case都差不多是log（N）吧，worst case是N
: ,所有子node全挂在一边了， 这个是用来测试你对tree是不是了解基础知识吧。
: 如果题目是很specific的一个tree的话，那我觉得也是遍历了。
: 等高手
|
s********a
发帖数: 1447 | 5 我也觉得是啊~
【在 r****o 的大作中提到】
: 找二叉树的高度不是O(n)吗？
:
: 是N
|
l*****a
发帖数: 14598 | 6 请问这是算法题还是？
回答:root node到leaf node的最大路径，咋样？
【在 K******g 的大作中提到】
: 如果有人问你 Height of a BInary tree.
: 请问怎么回答？
|
y**i
发帖数: 1112 | 7 如果要遍历，是用广度优先遍历么？最后一个元素的层高就是高度对吧？ |
d**e
发帖数: 6098 | 8 看起来递归比较简单
int height(Node * node)
{
if(!node)
return 0;
int lh = height(node->left) + 1;
int rh = height(node->right) + 1;
return (lh > rh ? lh : rh);
}
【在 y**i 的大作中提到】
: 如果要遍历，是用广度优先遍历么？最后一个元素的层高就是高度对吧？
|
y**i
发帖数: 1112 | 9 嗯，这个最好，不用遍历，时间复杂度O(n)，只是空指针的情况下返回值是不是应该改
成-1？树的高度定义是不包括根结点的吧
【在 d**e 的大作中提到】
: 看起来递归比较简单
: int height(Node * node)
: {
: if(!node)
: return 0;
: int lh = height(node->left) + 1;
: int rh = height(node->right) + 1;
: return (lh > rh ? lh : rh);
: }
|
y**i
发帖数: 1112 | 10 他说的average和best case是log(N)指的是树的高度不是时间复杂度吧，你说的应该是
算法的时间复杂度
【在 r****o 的大作中提到】
: 找二叉树的高度不是O(n)吗？
:
: 是N
|
d**e
发帖数: 6098 | 11 对……我也没想清楚，呵呵
【在 y**i 的大作中提到】
: 嗯，这个最好，不用遍历，时间复杂度O(n)，只是空指针的情况下返回值是不是应该改
: 成-1？树的高度定义是不包括根结点的吧
|
g*****u
发帖数: 298 | 12 这怎么不是遍历了？
求树的高度，一定得遍历（假设你没有additional info）。如果你漏掉某个节点，得
到的结果就可能是错误的。
还有，我觉得用recursion都要考虑个recursion level的问题，很容易stack overflow
的。
【在 y**i 的大作中提到】
: 嗯，这个最好，不用遍历，时间复杂度O(n)，只是空指针的情况下返回值是不是应该改
: 成-1？树的高度定义是不包括根结点的吧
|
