题目链接：Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.
OJ’s Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.
这道题的要求是回复二叉搜索树中2个因交换顺序而出错的元素。要求不改变二叉搜索树结构。
二叉搜索树，顾名思义，它是一个二叉树，即每个节点下面最多有2个子节点。同时为了便于搜索的特性，二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
- 若其左子树不空，则左子树上所有结点的值均小于根结点的值；
- 若其右子树不空，则右子树上所有结点的值均大于根结点的值；
- 其左、右子树也分别为二叉搜索树。
二叉搜索树还有个特点就是中序遍历是严格递增的，因此可以利用个特性查找顺序出错的位置。
和Validate Binary Search Tree类似的二叉搜索树题目，同样采用pre记录前一节点，然后对二叉树进行中序遍历，同时检测pre节点的数字是否小样当前节点的数字。如果发现pre节点的数字大于当前节点，这说明此处元素顺序不正确。然后分别用n1和n2两个指针记录顺序不正确的位置，最后交换n1和n2指向的节点中的数字即可。
由于只有2个元素的位置出错，需要交换过来，因此共有2种情况：
- 如果这两个元素相邻，例如中序遍历后的顺序为：1 -> 2 -> 4 -> 3 -> 5 -> 6（错误的交换了3和4的顺序），则在中序遍历的时候，只会出现一次顺序不正确，就是pre指向4的时候（此时的当前节点为3）。因此，只需要令n1指向4，n2指向3即可。
- 如果这两个元素不相邻，例如中序遍历后的顺序为：1 -> 5 -> 3 -> 4 -> 2 -> 6（错误的交换了2和5的顺序），则在中序遍历的时候，就会出现两次顺序不正确，分别是pre指向5的时候（此时的当前节点为3）和pre指向4的时候（此时的当前节点为2）。因此，只需要令n1指向5，n2指向2即可。
综上所述，中序遍历过程中检测到顺序不正确的时候，n1需要指向pre指向的节点，n2需要指向当前节点。为了兼顾上面两种情况，n1只在第一次检测到顺序不正确的时候指向pre指向的节点，而n2只要在检测到顺序不正确的时候就指向当前节点即可。
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
void recoverTree(TreeNode *root)
{
TreeNode *n1 = NULL, *n2 = NULL, *pre = NULL;
inorderTraversal(root, n1, n2, pre);
swap(n1 -> val, n2 -> val);
}
private:
void inorderTraversal(TreeNode *p, TreeNode *&n1, TreeNode *&n2, TreeNode *&pre)
{
if(p == NULL)
return;
inorderTraversal(p -> left, n1, n2, pre);
if(pre != NULL && pre -> val > p -> val && n1 == NULL)
n1 = pre;
if(pre != NULL && pre -> val > p -> val && n1 != NULL)
n2 = p;
pre = p;
inorderTraversal(p -> right, n1, n2, pre);
}
};