原来是美男？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>TVChinese - 中文电视

原来是美男？

原来是美男？# TVChinese - 中文电视

S*Y2013-09-09 07:09

1 楼

plz implement a non-recursive post order tree traversal.
I think this is difficult. It is kinda simple for pre-order and in-order, bu
t post-order is tough.

b*82013-09-09 07:09

2 楼

想邀请父母来美国呆一段时间，老爸以前持因公护照去过香港、澳门、台湾和印度，这
次他办了个因私护照，打算持因私护照到美国来（因为因公护照一直被单位收着，不容
易要出来）。
如果VO问我爸去过其他国家没有，我爸该怎么回答啊？
如果回答去过，那VO是不是会有疑问，为什么护照上没有签证，会要因公护照看吧？
如果回答没去过，是不是算撒谎啊？
好纠结啊……

l*t2013-09-09 07:09

3 楼

我的L1B的I94在2019年4月2号过期，请问我能参加2019年的H1B抽签吗

z*i2013-09-09 07:09

4 楼

9月6日，韩国艺人张根硕来到深圳为代言品牌活动站台，在接受媒体采访时，他发挥自
恋本色，自认是亚洲最漂亮的男人。
张根硕另外两张照片
切？晕死。为什么相机不是关西1号？
快乐大本营张根硕

r*o2013-09-09 07:09

5 楼

why post-order is tough?

bu

【在 S**Y 的大作中提到】

: plz implement a non-recursive post order tree traversal.
: I think this is difficult. It is kinda simple for pre-order and in-order, bu
: t post-order is tough.

a*n2013-09-09 07:09

6 楼

老实说，你们可以准备点去过的照片。

【在 b**********8 的大作中提到】

: 想邀请父母来美国呆一段时间，老爸以前持因公护照去过香港、澳门、台湾和印度，这
: 次他办了个因私护照，打算持因私护照到美国来（因为因公护照一直被单位收着，不容
: 易要出来）。
: 如果VO问我爸去过其他国家没有，我爸该怎么回答啊？
: 如果回答去过，那VO是不是会有疑问，为什么护照上没有签证，会要因公护照看吧？
: 如果回答没去过，是不是算撒谎啊？
: 好纠结啊……

z*i2013-09-09 07:09

7 楼

还是头发短的时候好看

S*Y2013-09-09 07:09

8 楼

code it :)

【在 r****o 的大作中提到】

: why post-order is tough?
:
: bu

b*82013-09-09 07:09

9 楼

嗯，这倒是个主意，呵呵。
那就是说如果签证官问去过哪些国家和地方，我爸就老实回答去过哪哪哪，然后说是拿
着因公护照去的，因公护照在单位，个人不能随便拿出来，有去过的照片，然后递给VO
这样行吗？

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

: 老实说，你们可以准备点去过的照片。

y*i2013-09-09 07:09

10 楼

难道不是亚洲最美丽的美女？

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

: 还是头发短的时候好看

f*r2013-09-09 07:09

11 楼

use standard techniques to convert the recursive function to non-recursive
function. almost same as in and pre orders.
void postOrder() {
Node *p = root, *pre = 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 == pre) {
visit(p);
st.pop();
pre = p;
p = NULL;
}
else

【在 S**Y 的大作中提到】

: plz implement a non-recursive post order tree traversal.
: I think this is difficult. It is kinda simple for pre-order and in-order, bu
: t post-order is tough.

a*n2013-09-09 07:09

12 楼

对呀，有证明不是证明你说谎就好，其实很大可能签证官也不会看。

VO

【在 b**********8 的大作中提到】

: 嗯，这倒是个主意，呵呵。
: 那就是说如果签证官问去过哪些国家和地方，我爸就老实回答去过哪哪哪，然后说是拿
: 着因公护照去的，因公护照在单位，个人不能随便拿出来，有去过的照片，然后递给VO
: 这样行吗？

a*a2013-09-09 07:09

13 楼

男不男，女不女

S*Y2013-09-09 07:09

14 楼

cool.you are so fast.
could you give more hint(or a link/book) about "standard techniques to conve
rt the recursive func to non-recursive func."?
It cost me much time and brain to convert it myself.. thanks a lot.

【在 f*********r 的大作中提到】

: use standard techniques to convert the recursive function to non-recursive
: function. almost same as in and pre orders.
: void postOrder() {
: Node *p = root, *pre = root;
: stack st;
: int i = 0;
: while(!st.empty() || p){
: while(p){
: st.push(p);
: p = p->left;

z*i2013-09-09 07:09

15 楼

难道现在南韩的潮流不是这样？

f*r2013-09-09 07:09

16 楼

you will find those kind of techniques in the book "Algorithms in C", author
conve

J*i2013-09-09 07:09

17 楼

在贝多芬病毒里很受看，没那么娘。

g*y2013-09-09 07:09

18 楼

我这个不用stack，queue这些
貌似有的面试可能会有这个要求。
while(root->left || root->right){
if (root->left){
root = root->left;
}else{
root = root->right;
}
}
do{
print(root);
if( root = root->p->left){
if(root->p->right){
root = root->p->right;
}else{
root = root->p;
}
}else{
root = root->p;
}
}while(root->p)

x*h2013-09-09 07:09

19 楼

郭敬明

S*Y2013-09-09 07:09

20 楼

but u r changing the Node data structure?

【在 g*******y 的大作中提到】

: 我这个不用stack，queue这些
: 貌似有的面试可能会有这个要求。
: while(root->left || root->right){
: if (root->left){
: root = root->left;
: }else{
: root = root->right;
: }
: }
: do{

l*12013-09-09 07:09

21 楼

不男不女的人看着最恶心！

g*y2013-09-09 07:09

22 楼

树的data structure中，link to parent 还是很常见吧
再说了，总得花额外的空间。
我只是假设面试的人要求不能用stack/queue但是有node->p的话，这个比用stack什么的，难度稍微增加一点点。其实时间和空间差不多的。如果你要考虑stack可能会resize什么的话，我这个还好些。

【在 S**Y 的大作中提到】

: but u r changing the Node data structure?

z*i2013-09-09 07:09

23 楼

娘是一种趋势，“没有最娘，只有更娘！”

f*r2013-09-09 07:09

24 楼

I don't think it's possible for standard tree structure.

【在 g*******y 的大作中提到】

L*a2013-09-09 07:09

25 楼

第一张这种，国内有很多吧，不少选秀看到类似的。

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

: 还是头发短的时候好看

g*y2013-09-09 07:09

26 楼

come on, we are talking about interview prob, interviewer can have any version
of tree he wants, to make the problem slightly harder.

【在 f*********r 的大作中提到】

: I don't think it's possible for standard tree structure.

v*a2013-09-09 07:09

27 楼

现在国内好这口，所为花美男，女汉子

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

: 不男不女的人看着最恶心！

g*y2013-09-09 07:09

28 楼

yes I agree.
stack size is h
it's the queue for BFS that costs O(N);

【在 f*********r 的大作中提到】

: I don't think it's possible for standard tree structure.

D*r2013-09-09 07:09

29 楼

这个是日韩先发起的
中国虽然跟进了，但毕竟还没那么主流

【在 v******a 的大作中提到】

: 现在国内好这口，所为花美男，女汉子

f*r2013-09-09 07:09

30 楼

I also think if you have pointer to parent in the tree structure, most of
the tree problems will become easier.

【在 g*******y 的大作中提到】

: yes I agree.
: stack size is h
: it's the queue for BFS that costs O(N);

v*a2013-09-09 07:09

31 楼

我看现在越来越多了

【在 D***r 的大作中提到】

: 这个是日韩先发起的
: 中国虽然跟进了，但毕竟还没那么主流

f*r2013-09-09 07:09

32 楼

just like the problems for the doubly linked list is much easier than the
same problem for the singly linked list.

【在 f*********r 的大作中提到】

: I also think if you have pointer to parent in the tree structure, most of
: the tree problems will become easier.

S*n2013-09-09 07:09

33 楼

这个人不来演兰陵王，真是太可惜了。

S*Y2013-09-09 07:09

34 楼

just found the book you mentioned.thanks.
it is very comprehensive book, my first impression..hehe

【在 f*********r 的大作中提到】

: just like the problems for the doubly linked list is much easier than the
: same problem for the singly linked list.

n*22013-09-09 07:09

35 楼

长的有让人吐的冲动，最烦这种不男不女的人了

f*r2013-09-09 07:09

36 楼

动作真快~.

【在 S**Y 的大作中提到】

: just found the book you mentioned.thanks.
: it is very comprehensive book, my first impression..hehe

l*12013-09-09 07:09

37 楼

这就是阴盛阳衰吧？世道要变了么？好可怕！

【在 v******a 的大作中提到】

: 现在国内好这口，所为花美男，女汉子

S*Y2013-09-09 07:09

38 楼

k*l2013-09-09 07:09

39 楼

确实贝多芬病毒里的小警察还能看。
后面美男走视觉系歌手路线还算凑合剧情。
再后面一发不可收拾的娘了就特别油腻，完全不能看了。

g*y2013-09-09 07:09

40 楼

insteresting idea...
any example tree problem in your mind? I think I've done too few problems
to see a really difficult one.
if most tree problems will become easier with parent link, why don't they
just have one? hehe

【在 f*********r 的大作中提到】

: I also think if you have pointer to parent in the tree structure, most of
: the tree problems will become easier.

c*d2013-09-09 07:09

41 楼

真的是男的?

f*r2013-09-09 07:09

42 楼

en, you are right~

【在 g*******y 的大作中提到】

: insteresting idea...
: any example tree problem in your mind? I think I've done too few problems
: to see a really difficult one.
: if most tree problems will become easier with parent link, why don't they
: just have one? hehe

z*i2013-09-09 07:09

43 楼

这也是男性？
ref:
http://www.mitbbs.com/news_wenzhang/Headline/31627793.html

g*y2013-09-09 07:09

44 楼

by the way, your code seems not working

【在 f*********r 的大作中提到】

f*r2013-09-09 07:09

45 楼

maybe not right, I didn't test it. watching movie now

【在 g*******y 的大作中提到】

: by the way, your code seems not working

g*y2013-09-09 07:09

46 楼

我改了一下:
void findNext(Node *node, stack &stk)){
while(node->left || node->right){
stk.push(node);
node = (node->left)? node->left : node->right;
}
stk.push(node);
}
void post2(Node *root){
if(!root) return;
stack stk;
Node *node, *pre;
findNext(root,stk);
pre = stk.top(); visit(pre); stk.pop();
while(!stk.empty()){
node = stk.top();
if(node->right==0 || node->right == pre){
visit(node); stk.pop(); pre =

【在 f*********r 的大作中提到】

: maybe not right, I didn't test it. watching movie now

s*e2013-09-09 07:09

47 楼

public void postOrderTraversal(TreeNode root)
{
Stack s = new Stack();
s.push(root);
while(!s.isEmpty())
{
TreeNode node = (TreeNode)s.peek();
if(node.left != null && !node.left.visited)
s.push(node.left);
else if(node.right != null && !node.right.visited)
s.push(node.right);
else
{
System.out.print(node.value+" ");
node.visited = true;
s.pop();
}
}

s*e2013-09-09 07:09

48 楼

en, just tested, it worked..

g*y2013-09-09 07:09

49 楼

你用了 .visited ，简化了问题

【在 s*******e 的大作中提到】

: public void postOrderTraversal(TreeNode root)
: {
: Stack s = new Stack();
: s.push(root);
: while(!s.isEmpty())
: {
: TreeNode node = (TreeNode)s.peek();
: if(node.left != null && !node.left.visited)
: s.push(node.left);
: else if(node.right != null && !node.right.visited)

S*Y2013-09-09 07:09

50 楼

ft..
it is really confusing to look at people's code without comments
Can u comment it?

【在 g*******y 的大作中提到】

: 我改了一下:
: void findNext(Node *node, stack &stk)){
: while(node->left || node->right){
: stk.push(node);
: node = (node->left)? node->left : node->right;
: }
: stk.push(node);
: }
: void post2(Node *root){
: if(!root) return;

g*y2013-09-09 07:09

51 楼

void FindLeftmostLeaf(Node *root, stack &stk){
while(root->left || root->right){ //while(当前节点不是叶子)
stk.push(root);
if (root->left){
root = root->left;
}else{
root = root->right;
}
}
stk.push(root);
}
void PostOrder(Node *root){
if(root) return; //check empty tree;
stack stk;
Node *node=root, *parent;
//找子树中最左边的叶子，并把途中的节点放入栈
FindLeftmostLeaf(root,stk);
while(!stk.empty()){
node

【在 S**Y 的大作中提到】

: ft..
: it is really confusing to look at people's code without comments
: Can u comment it?

c*e2013-09-09 07:09

52 楼

void tranverse(node *root){
vector stack;
node *p;
node *np;
stack.push_back(root);
while(stack.size()>0){
p=stack.back();
if(p->left==NULL&&p->right==NULL)
cout<data;//只有terminal 节点才被输出
else{
stack.pop_back();
np=new node;//把visit过的节点copy成terminal, 以后再输出
np->left=np->right=NULL;
np->data=p.data;
stack.push_pack(np);
}
if(p->right!=NULL)
stack.push_pack(p->right);
if(p->left!=NULL)
stack.push_pack(p->le

g*y2013-09-09 07:09

53 楼

嗯，比较简洁。不过代价是你得复制一次data，这个就得考虑data的大小了，而且还有
不少限制，比如data的type是否允许copy，或者visit不一定是只读的过程。。。

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

: void tranverse(node *root){
: vector stack;
: node *p;
: node *np;
: stack.push_back(root);
: while(stack.size()>0){
: p=stack.back();
: if(p->left==NULL&&p->right==NULL)
: cout<data;//只有terminal 节点才被输出
: else{

C*n2013-09-09 07:09

54 楼

老大你太牛了，
能说说思路吗？
我看明白了但是还是觉得挺难的。

【在 g*******y 的大作中提到】

: void FindLeftmostLeaf(Node *root, stack &stk){
: while(root->left || root->right){ //while(当前节点不是叶子)
: stk.push(root);
: if (root->left){
: root = root->left;
: }else{
: root = root->right;
: }
: }
: stk.push(root);

h*i2013-09-09 07:09

55 楼

possible error: if(!stk.empty()) return;
should be
if(stk.empty()) return;

【在 g*******y 的大作中提到】

g*y2013-09-09 07:09

56 楼

haha,my shame~

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

: possible error: if(!stk.empty()) return;
: should be
: if(stk.empty()) return;

C*n2013-09-09 07:09

57 楼

hehe, 还有if (root) return -> if (!root) return
能说说解这种题的思路吗？

【在 g*******y 的大作中提到】

: haha,my shame~

g*y2013-09-09 07:09

58 楼

sigh...too many careless flaws...
思路其实跟我前面发的那个code，不用stack，但是假设每个node都有个parent link。
这个用stack的版本，只不过就是用stack记录了必要的一串parent而已。
另外一个想法是，假设我现在的stack里面有一堆正确的，必要的元素了，并且top的那
个就是当前需要visit的。那么在visit它后，应该做什么？加入新的元素并始终保持最
top的那个element in stack是当前需要visit的node? 或者pop掉? pop掉后，stack里
面next的元素应该是什么。

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

: hehe, 还有if (root) return -> if (!root) return
: 能说说解这种题的思路吗？

h*i2013-09-09 07:09

59 楼

暇不掩玉，
牛人，赞一下！

【在 g*******y 的大作中提到】

: haha,my shame~

S*Y2013-09-09 07:09

60 楼

your first version doesn't work. :)
but i like your second version very much, which makes it very straightforwar
d by using the FindNextEle function.

【在 g*******y 的大作中提到】

: sigh...too many careless flaws...
: 思路其实跟我前面发的那个code，不用stack，但是假设每个node都有个parent link。
: 这个用stack的版本，只不过就是用stack记录了必要的一串parent而已。
: 另外一个想法是，假设我现在的stack里面有一堆正确的，必要的元素了，并且top的那
: 个就是当前需要visit的。那么在visit它后，应该做什么？加入新的元素并始终保持最
: top的那个element in stack是当前需要visit的node? 或者pop掉? pop掉后，stack里
: 面next的元素应该是什么。

g*y2013-09-09 07:09

61 楼

呵呵，谢谢指出。不过我昨天也看到这个错误了，只是在自己电脑上改了，不过没有post出来。既然有人指出来，呵呵，我就Post一下吧。省略掉了判断empty啊，是不是null指针等细节。可以看出来，这个用Parent指针的方法，跟用stack的版本非常的相似。
void nextPost(Node *&root){ //还是找最左的叶子
while(root->left || root->right){
if (root->left){
root = root->left;
}else{
root = root->right;
}
}
}
void post_traversal(Node *root){
nextPost(root); //图简便，省去trival的判断了，直接找最左叶子
while(root->p){ //while不是根节点
visit(root);
if( root == root->p->left){ /

【在 S**Y 的大作中提到】

: your first version doesn't work. :)
: but i like your second version very much, which makes it very straightforwar
: d by using the FindNextEle function.