recover binary search tree 常数空间 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

recover binary search tree 常数空间

recover binary search tree 常数空间# JobHunting - 待字闺中

m*12012-11-12 08:11

1 楼

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
如果中序遍历后存起来自然是好解决，可是不满足空间要求，如何在O(1)空间做到？

c*t2012-11-12 08:11

2 楼

in order traverse不存,只存前一个node，比较current与前一个的值。
如果只有一次不满足 current.val >= previous.val, swap their values.
如果有两次不满足，记录第一次的 previous 和第二次的current, swap their values

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

: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: 如果中序遍历后存起来自然是好解决，可是不满足空间要求，如何在O(1)空间做到？

e*e2012-11-12 08:11

3 楼

Inorder traverse, keep the prev value and prev tree node,
Find first misplaced node by
if ( current.val < prev.val )
Node first = prev;
Find second by
if ( current.val < prev.val )
Node second = current;
After traversal, swap the values of first and second node.
Only need two pointers, prev and current node, and two variables, first and
second node. O(1) space.