b**u
发帖数: 45 | 1 http://oj.leetcode.com/problems/recover-binary-search-tree/
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
note说O(n) space straightforward，我怎么不觉得？要结构和原来一样，想不出O(n)
有什么明显解法。谁说说思路？ |
A*********c
发帖数: 430 | 2 inorder遍历，此过程中建立两个数组，一个顺序存所有的Node地址，一个顺序存所有
的node值。
这步，相当于建立了一对儿parallel array.
Inorder产生的值数组应该是排好序的，但是不是，因为两个值错位了。
linear scan值数组。找到错位的两个index，然后去对调node地址array中相应的index
，这步是O(n), O(1).
n)
【在 b**u 的大作中提到】
: http://oj.leetcode.com/problems/recover-binary-search-tree/
: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: note说O(n) space straightforward，我怎么不觉得？要结构和原来一样，想不出O(n)
: 有什么明显解法。谁说说思路？
|
y*****3
发帖数: 451 | 3 不是很懂LZ在说什么，为什么保持结构一样就无法O(n) space了？
n)
【在 b**u 的大作中提到】
: http://oj.leetcode.com/problems/recover-binary-search-tree/
: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: note说O(n) space straightforward，我怎么不觉得？要结构和原来一样，想不出O(n)
: 有什么明显解法。谁说说思路？
|
l******a
发帖数: 64 | 4 中序遍历，记录不符合顺序的情况，in place 替换，时间复杂度O(n), 空间复杂度O(1
) |
