【每日算法Day 73】学妹大半夜私聊我有空吗，然后竟然做出这种事！

输入：
[1,3,null,null,2]
   1
  /
 3
  \
   2
输出：
[3,1,null,null,2]
   3
  /
 1
  \
   2

输入：
[3,1,4,null,null,2]
  3
 / \
1   4
   /
  2
输出：
[2,1,4,null,null,3]
  2
 / \
1   4
   /
  3

/**
 * 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) {
        TreeNode *x = NULL, *y = NULL, *pre = NULL, *rightmost = NULL;
        while (root) {
            // 如果有左子树，就递归遍历左子树。
            if (root->left) {
                rightmost = root->left;
                // 找出左子树的最右边一个叶子结点
                while (rightmost->right && rightmost->right != root) {
                    rightmost = rightmost->right;
                }
                // 如果左子树最右边的叶子结点的右儿子是空的，
                // 那就说明根结点是第一次访问，那么就把它的右儿子指向根结点。
                // 然后递归遍历左子树。
                if (rightmost->right != root) {
                    rightmost->right = root;
                    root = root->left;
                // 否则的话说明根结点是第二次访问了，
                // 那就说明左子树已经递归完毕了，
                // 那么就判断一下是否存在逆序对。
                // 记得把左子树最右叶子结点的右儿子改回空指针。
                // 然后递归遍历右子树了。
                } else {
                    if (pre && pre->val > root->val) {
                        if (x == NULL) x = pre;
                        y = root;
                    }
                    rightmost->right = NULL;
                    pre = root;
                    root = root->right;
                }
            // 如果没有左子树，那就直接遍历右子树，同时判断是否存在逆序对。
            } else {
                if (pre && pre->val > root->val) {
                    if (x == NULL) x = pre;
                    y = root;
                }
                pre = root;
                root = root->right;
            }
        }
        swap(x->val, y->val);
    }
};