m*******1
发帖数: 77 | 1 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
如果中序遍历后存起来自然是好解决，可是不满足空间要求，如何在O(1)空间做到？ | c********t
发帖数: 5706 | 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****e
发帖数: 418 | 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. |
|
