我碰到的apple map问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Apple - 家有苹果

我碰到的apple map问题

我碰到的apple map问题# Apple - 家有苹果

d*n2012-09-28 07:09

1 楼

Do postorder traversal without using recursion.
You can't modify the tree node struct which is as following:
struct Node {
int data;
Node *left;
Node *right;
}
If you want to use stack, use no more than 1 stack.
Any idea?:

l*u2012-09-28 07:09

2 楼

看了一間房，在主要道路旁.我不擔心噪音。但是聽說主路旁的房子比較不安全。是真
的嗎?

s*v2012-09-28 07:09

3 楼

说起来也搞笑，去买iphone 5 case, 输进去地址，是个大community，指在整个
community中央，这到没啥。关键是route不对，离着还有2个block就断了。google map
从来没有过这样的错，apple map第一次就这样。

B*t2012-09-28 07:09

4 楼

贴个代码仅供参考
void postOrder() {
Node *p = root, *visited = root;
stack st;
int i = 0;
while(!st.empty() || p){
while(p){
st.push(p);
p = p->left;
}
p = st.top();
if(p->right == NULL || p->right == visited) {
visit(p->c);
st.pop();
visited = p;
p = NULL;
}
else
p = p->right;
}
}

【在 d****n 的大作中提到】

: Do postorder traversal without using recursion.
: You can't modify the tree node struct which is as following:
: struct Node {
: int data;
: Node *left;
: Node *right;
: }
: If you want to use stack, use no more than 1 stack.
: Any idea?:

c*h2012-09-28 07:09

5 楼

离开半麦比较好
再说你家小孩玩耍也不希望跑道路上去

d*n2012-09-28 07:09

6 楼

Nice, saved to my library. Thanks.

【在 B*****t 的大作中提到】

: 贴个代码仅供参考
: void postOrder() {
: Node *p = root, *visited = root;
: stack st;
: int i = 0;
: while(!st.empty() || p){
: while(p){
: st.push(p);
: p = p->left;
: }

l*u2012-09-28 07:09

7 楼

裡面的房至少貴四五萬，糾結中

【在 c********h 的大作中提到】

: 离开半麦比较好
: 再说你家小孩玩耍也不希望跑道路上去

m*g2012-09-28 07:09

8 楼

不是很明白。高手评价一下：
void postOrderTraversal(node *root)
{

stack st;
st.push(root);
st.push(root);
node *curNode;
node *visited;
while(!st.empty())
{
visited=st.top();
st.pop();
curNode=st.top();
st.pop();
if(!(curNode->left&&curNode->right)) {printf(curNode); st.push(curNode)
; continue;}
if(curNode->left && (curNode->left != visited))
{ st.push(curNode);
if(curNode->right) st.push(curNode->right);
st.push(curNode->left);

【在 d****n 的大作中提到】

q*m2012-09-28 07:09

9 楼

我家的情况，里面的房子贵40万，呵呵

【在 l****u 的大作中提到】

: 裡面的房至少貴四五萬，糾結中

z*j2012-09-28 07:09

10 楼

说说我的理解:
基本上是在用栈模拟递归的后序遍历过程
对栈顶node, 要判断这个node是回溯过来的,还是刚push到栈顶的
case1:栈顶node左右孩子皆空, 到了叶节点.接下来就要回溯啦.
case2:左孩子回溯回来, 则访问右孩子(2sub cases)
case3:右孩子回溯回来, 则访问栈顶节点, 同时栈顶节点出栈
剩下case 是栈顶不是回溯回来的, 则继续压栈(深度优先搜索)

g*92012-09-28 07:09

11 楼

All depends.
Picture? Link?
How much traffic will go through this road every day?
You worried about crime or tire dust? Still not sure what kind of 不安全 you
are concerned about.

【在 l****u 的大作中提到】

: 看了一間房，在主要道路旁.我不擔心噪音。但是聽說主路旁的房子比較不安全。是真
: 的嗎?

c*n2012-09-28 07:09

12 楼

我想问下这是面试完以后给布置的么？

【在 d****n 的大作中提到】

b*l2012-09-28 07:09

13 楼

安全是一个问题，另外你在交通高峰时进出及其不方便。孩子也没有什么地方玩耍。

【在 l****u 的大作中提到】

: 看了一間房，在主要道路旁.我不擔心噪音。但是聽說主路旁的房子比較不安全。是真
: 的嗎?

l*s2012-09-28 07:09

14 楼

我的想法和你类似，但不尽一样：
1. if root is empty, return
2. stack.push(root)
3. let prev_print point to the previous node printed. initially, it points
to a dummy node.
3. while stack is not empty
4. case 1: stack.top is a leaf node. print it.
let prev_print point to stack.top. pop stack.
5. case 2: prev_print is a child of stack.top.
let prev_print point to stack.top. pop stack.
6. case 3: otherwise.
push stack.top's children to stack in right first o

【在 z*j 的大作中提到】

: 说说我的理解:
: 基本上是在用栈模拟递归的后序遍历过程
: 对栈顶node, 要判断这个node是回溯过来的,还是刚push到栈顶的
: case1:栈顶node左右孩子皆空, 到了叶节点.接下来就要回溯啦.
: case2:左孩子回溯回来, 则访问右孩子(2sub cases)
: case3:右孩子回溯回来, 则访问栈顶节点, 同时栈顶节点出栈
: 剩下case 是栈顶不是回溯回来的, 则继续压栈(深度优先搜索)

l*q2012-09-28 07:09

15 楼

有简单的做法：
p = q = root;
while(p!=0)
{
for( ; p->left! = 0 ; p = p->left)
stack.push(p);
while(p != 0 && ( p->right == 0 || p->right == q))
{
//print p
q = p;
if(stack.empty())
return;
p = stack.pop();
}
stack.push(p);
p = p->right;
}
简化在于两点：叶子不要push in； pop out之后的可以再push in