w********s
发帖数: 214 | 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.
谢谢 |
w********s
发帖数: 214 | 2 而且这个题目描述貌似有一些瑕疵，如果是recursion的话还能是O(1) space么？
貌似比较被推崇的答案都是recursive inorder traverse+two pointers.这个应该不能
算是constant space了吧？
如果哪位有flawless的java solution，希望能分享一下。 |
D******y
发帖数: 316 | 3 同问
★ 发自iPhone App: ChineseWeb 8.1
【在 w********s 的大作中提到】
: 而且这个题目描述貌似有一些瑕疵，如果是recursion的话还能是O(1) space么？
: 貌似比较被推崇的答案都是recursive inorder traverse+two pointers.这个应该不能
: 算是constant space了吧？
: 如果哪位有flawless的java solution，希望能分享一下。
|
w********s
发帖数: 214 | |
l*n
发帖数: 529 | 5 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.
: 谢谢
|
