a***e 发帖数: 413 | 1 最近几天的少得可怜的准备时间都在看这个。60多行程序改个地方就通不过了。区别仅
在于
while(1)
{
r.push_back(p->val);
if(p==from)
break;
p = p->right;
}
不能改成
while(p!=from)
{
r.push_back(p->val);
p = p->right;
}
哎,可能还是因为这个算法不是自己想出来的,总是糊涂。
偶尔说起来,别人说那种属于比较偏的题了,如果问道肯定是存心要fail某人。
就是好奇有没有人真被问到。
能通过OJ的,
void reverse(TreeNode *from, TreeNode *to)
{
if (from==to)
return;
TreeNode *x = from, *y = from->right, *z;
while(x!=to){
z=y->right;
y->right = x;
x = y;
y = z;
}
}
void getReverse(TreeNode *from, TreeNode *to, vector &r)
{
reverse(from,to);
TreeNode *p = to;
while(1)
{
r.push_back(p->val);
if(p==from)
break;
p = p->right;
}
reverse(to,from);
}
vector postorderTraversal(TreeNode *root) {
vector ret;
if(root==NULL)
return ret;
TreeNode dump(0);
dump.left = root;
TreeNode *cur = &dump, *prev = NULL;
while(cur)
{
if (cur->left==NULL)
cur = cur->right;
else
{
prev = cur->left;
while(prev->right!=NULL&&prev->right!=cur)
prev = prev->right;
if (prev->right==NULL)
{
prev->right = cur;
cur = cur->left;
}
else
{
getReverse(cur->left,prev,ret);
prev->right = NULL;
cur = cur->right;
}
}
}
}
不能通过的
void reverse(TreeNode *from, TreeNode *to)
{
if (from==to)
return;
TreeNode *x = from, *y = from->right, *z;
while(x!=to){
z=y->right;
y->right = x;
x = y;
y = z;
}
}
void getReverse(TreeNode *from, TreeNode *to, vector &r)
{
reverse(from,to);
TreeNode *p = to;
while(p!=from)
{
r.push_back(p->val);
p = p->right;
}
reverse(to,from);
}
vector postorderTraversal(TreeNode *root) {
vector ret;
if(root==NULL)
return ret;
TreeNode dump(0);
dump.left = root;
TreeNode *cur = &dump, *prev = NULL;
while(cur)
{
if (cur->left==NULL)
cur = cur->right;
else
{
prev = cur->left;
while(prev->right!=NULL&&prev->right!=cur)
prev = prev->right;
if (prev->right==NULL)
{
prev->right = cur;
cur = cur->left;
}
else
{
getReverse(cur->left,prev,ret);
prev->right = NULL;
cur = cur->right;
}
}
}
} | l*****a 发帖数: 14598 | 2 面什么厂啊,需要专门准备这个?
会个一般解法的就可以了吧
【在 a***e 的大作中提到】 : 最近几天的少得可怜的准备时间都在看这个。60多行程序改个地方就通不过了。区别仅 : 在于 : while(1) : { : r.push_back(p->val); : if(p==from) : break; : p = p->right; : } : 不能改成
| A*****i 发帖数: 3587 | 3 两年前有一个朋友被yelp问到,这是我唯一一次听说有人被问到这个算法的。
那也是第一次听说有这么个玩意儿存在 | b********r 发帖数: 620 | 4 以前上算法课的时候自己做过。面试没见过。
【在 A*****i 的大作中提到】 : 两年前有一个朋友被yelp问到,这是我唯一一次听说有人被问到这个算法的。 : 那也是第一次听说有这么个玩意儿存在
| i******t 发帖数: 22541 | | b******g 发帖数: 3616 | 6 Morris本来就挺复杂了.Morris Poster Order还是三种顺序访问里最难的一个.这个面
试考的话实在太变态了.面试官自己能半小时内写出来就很不错了... | h*********d 发帖数: 1054 | 7 it does not hurt to study if you have time. | M*******a 发帖数: 1633 | 8 我老想了一下好像morris traverse只能pre/in order,不能post order把,当然不排
除你自己想个post order的traverse但是估计也更morris差很远了吧。 |
|