由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 有没有面试被问到Binary Tree Postorder Traversal Morris Traversal的呢?
相关主题
感觉Binary Tree Postorder Traversal的iterative是三种traversal中最难的Construct Binary Tree from Inorder and Postorder Traversal
[leetcode] Binary Tree from Inorder & Postorder Traversal讨论一道leetcode上面的题
请教大家一个问题:Maximum Height (Depth) of a Binary Tree Using PreOrder Traversalflattern binary tree to linked list (leetcode)
inorder traversal的空间复杂度是O(N) 还是O(logN)?一个小面筋
Interview question::Print all the paths from root to every leaf 的 iterative
问几个有关Binary tree的题Tree的traversal也分BFS和DFS?
攒人品,amazon一面经历帮我看一下5行代码
问一道二叉树遍历的问题? 谢谢!遇到了一个很奇怪的C++问题
相关话题的讨论汇总
话题: cur话题: treenode话题: prev话题: right话题: null
进入JobHunting版参与讨论
1 (共1页)
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
5
这难道不属于刁难人?
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差很远了吧。
1 (共1页)
进入JobHunting版参与讨论
相关主题
遇到了一个很奇怪的C++问题Interview question::
[leetcode] Maximum Depth of Binary Tree问几个有关Binary tree的题
leetcode的OJ也会有错吗??攒人品,amazon一面经历
F家phone interview的一道题问一道二叉树遍历的问题? 谢谢!
感觉Binary Tree Postorder Traversal的iterative是三种traversal中最难的Construct Binary Tree from Inorder and Postorder Traversal
[leetcode] Binary Tree from Inorder & Postorder Traversal讨论一道leetcode上面的题
请教大家一个问题:Maximum Height (Depth) of a Binary Tree Using PreOrder Traversalflattern binary tree to linked list (leetcode)
inorder traversal的空间复杂度是O(N) 还是O(logN)?一个小面筋
相关话题的讨论汇总
话题: cur话题: treenode话题: prev话题: right话题: null