问一道leetcode题：recover BST - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道leetcode题：recover BST

问一道leetcode题：recover BST# JobHunting - 待字闺中

b*u2014-01-20 08:01

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*c2014-01-20 08:01

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)
: 有什么明显解法。谁说说思路？