LeetCode算法题目：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?

---

分析：

为了方便，我们用结点的值代替结点进行讨论。如果你把这棵二叉搜索树各结点的值用中序遍历的方式打印出来，那么就有一个位置上的数大于它后面相邻的数，之后又有一个位置上的数小于它前面相邻的数。这两个数正好相邻的情况再考虑。 于是，我们只需先找出那个大于它后一个数的数node1，再找出那个小于它前一个数的数node2，之后再交换两者的值就行了。要实现这一点，我们需要保存前一个结点pre，然后找到pre > cur这种反常的情况（共两次）。此时，若node1已经被找到了，则我们让 node2 = cur；否则，我们让 node1 = pre。 接下来我们考虑两个数相邻的情况。由于两个数相邻，我们只能找到一次 pre > cur 的情况，无法对node2进行赋值。但我们注意到，此时cur刚好就是我们要找的node2。再回到一般情况，就算此时的cur不是我们要找的node2，我们在后面第二次出现pre > cur的情况时，我们依旧会对node2赋值。所以，我们在第一次遇到pre > cur的情况时，分别将pre和cur赋值给node1和node2，在后面如果再次遇到pre > cur的情况，我们再将node2修改为正确的值，并保持node1的值不变。这样，我们总能找到正确的node1和node2。

代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void recoverTree(TreeNode *root) { node1 = node2 = pre = NULL; findout(root); swap(node1->val, node2->val); return; } void findout(TreeNode *root){ if (root->left != NULL) findout(root->left); if (pre != NULL){ if (pre->val > root->val){ if (node1 == NULL) node1 = pre, node2 = root; else node2 = root; } } pre = root; if (root->right != NULL) findout(root->right); } TreeNode *node1; TreeNode *node2; TreeNode *pre; };