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?

这题需要修复一颗二叉搜索树的两个交换节点数据，我们知道对于一颗二叉搜索树来说，如果按照中序遍历，那么它输出的值是递增有序的，所以我们只需要按照中序遍历输出，在输出结果里面找到两个异常数据（比它后面输出结果大），交换这两个节点的数据就可以了。

但是这题要求使用O(1)的空间，如果采用通常的中序遍历（递归或者栈）的方式，都需要O(N)的空间，所以这里我们用Morris Traversal的方式来进行树的中序遍历。

Morris Traversal中序遍历的原理比较简单：

  • 如果当前节点的左孩子为空，则输出当前节点并将其有孩子作为当前节点。
  • 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点，也就是当前节点左子树的最右边的那个节点。
    • 如果前驱节点的右孩子为空，则将它的右孩子设置为当前节点，当前节点更新为其左孩子。
    • 如果前驱节点的右孩子为当前节点，则将前驱节点的右孩子设为空，输出当前节点，当前节点更新为其右孩子。

重复上述过程，直到当前节点为空，递归的时候我们同时需要记录错误的节点。那么我们如何知道一个节点的数据是不是有问题呢？对于中序遍历来说，假设当前节点为cur，它的前驱节点为pre，如果cur的值小于pre的值，那么cur和pre里面的数据就是交换的了。

代码如下：

  1. class Solution {
  2. public:
  3.     void recoverTree(TreeNode *root) {
  4.         TreeNode* cur = 0;
  5.         TreeNode* pre = 0;
  6.         TreeNode* p1 = 0;
  7.         TreeNode* p2 = 0;
  8.         TreeNode* preCur = 0;
  10.         bool found = false;
  12.         if(!root) {
  13.             return;
  14.         }
  16.         cur = root;
  17.         while(cur) {
  18.             if(!cur->left) {
  19.                 //记录p1和p2
  20.                 if(preCur && preCur->val > cur->val) {
  21.                     if(!found) {
  22.                         p1 = preCur;
  23.                         found = true;
  24.                     }
  25.                     p2 = cur;
  26.                 }
  28.                 preCur = cur;
  29.                 cur = cur->right;
  30.             } else {
  31.                 pre = cur->left;
  32.                 while(pre->right && pre->right != cur) {
  33.                     pre = pre->right;
  34.                 }
  36.                 if(!pre->right) {
  37.                     pre->right = cur;
  38.                     cur = cur->left;
  39.                 } else {
  40.                     //记录p1和p2
  41.                     if(preCur->val > cur->val) {
  42.                         if(!found) {
  43.                             p1 = preCur;
  44.                             found = true;
  45.                         }
  46.                         p2 = cur;
  47.                     }
  48.                     preCur = cur;
  49.                     pre->right = NULL;
  50.                     cur = cur->right;
  51.                 }
  52.             }
  53.         }
  55.         if(p1 && p2) {
  56.             int t = p1->val;
  57.             p1->val = p2->val;
  58.             p2->val = t;
  59.         }
  60.     }
  61. };