寄出第一封请editor出示supporting letter,求bless - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Immigration - 落地生根

寄出第一封请editor出示supporting letter,求bless

寄出第一封请editor出示supporting letter,求bless# Immigration - 落地生根

w*s2012-08-28 07:08

1 楼

原题leetcode上可查：
就是一个BST中两个node被mistakenly swapped, find a solution to have it
restored.
要求用O(1) space.
看了网上的答案都是用cpp做in order traverse用指针记录两个点，然后swap。
青椒牛人有没有java的solution同样能达到O(1) space的结果呢？毕竟java没有指针，
想问问有没有其他的get around.
谢谢

m*52012-08-28 07:08

2 楼

犹豫很久后,终于厚着脸皮寄出第一封信.虽然帮他们审了5封稿件,但还是很不好意思,
毕竟当初是也是自己编了一堆堂而冠冕的理由去要求审稿的.
但是为了更充分,只能这样了.
求bless,期surprise.

w*s2012-08-28 07:08

3 楼

而且这个题目描述貌似有一些瑕疵，如果是recursion的话还能是O(1) space么？
貌似比较被推崇的答案都是recursive inorder traverse+two pointers.这个应该不能
算是constant space了吧？
如果哪位有flawless的java solution，希望能分享一下。

o*e2012-08-28 07:08

4 楼

bless

D*y2012-08-28 07:08

5 楼

同问

★ 发自iPhone App: ChineseWeb 8.1

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

: 而且这个题目描述貌似有一些瑕疵，如果是recursion的话还能是O(1) space么？
: 貌似比较被推崇的答案都是recursive inorder traverse+two pointers.这个应该不能
: 算是constant space了吧？
: 如果哪位有flawless的java solution，希望能分享一下。

k*x2012-08-28 07:08

6 楼

bless

w*s2012-08-28 07:08

7 楼

自己顶一下

b*r2012-08-28 07:08

8 楼

bless

l*n2012-08-28 07:08

9 楼

java的话，你可以用伪指针实现同样的设计，就是在c++用pointer的地方用一个
TreeNode[]。至于后面你问到的stack的问题，这个没有办法。inorder traversal的非
递归方法也需要stack，这样一来不用stack的话是没办法搞的，所以递归方法也不算是
有空间上的优势。非递归的好处在这里主要是显式stack是在heap分配空间的，而隐式
stack是在stack frame上，前者更不怕stack overflow，毕竟heap 比stack frame大得
多得多。

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

: 原题leetcode上可查：
: 就是一个BST中两个node被mistakenly swapped, find a solution to have it
: restored.
: 要求用O(1) space.
: 看了网上的答案都是用cpp做in order traverse用指针记录两个点，然后swap。
: 青椒牛人有没有java的solution同样能达到O(1) space的结果呢？毕竟java没有指针，
: 想问问有没有其他的get around.
: 谢谢

m*52012-08-28 07:08

10 楼

多谢多谢.