恢复二叉搜索树（常数空间实现）

题目：https://leetcode-cn.com/problems/recover-binary-search-tree/ 参考：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/cliang-chong-fang-fa-1shi-yong-di-gui-de-zhong-xu-/ 递归实现 （还可以用栈实现，不过也是O(n)空间的，此处略

/**
 * 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 dfs(TreeNode *root) {
        if(root->left != nullptr)
            dfs(root->left);
        if(p1 == nullptr && pre->val > root->val)
            p1 = pre;
        if(p1 != nullptr && pre->val > root->val)
            p2 = root;
        pre = root;
        if(root->right != nullptr)
            dfs(root->right);
    }
    void recoverTree(TreeNode* root) {
        pre = new TreeNode(INT_MIN);
        dfs(root);
        swap(p1->val,p2->val);
    }
private:
    TreeNode *p1,*p2,*pre;
};

循环实现，O(1)空间

/**
 * 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 solve(TreeNode *root) {
        while(root != nullptr) {
            if(root->left != nullptr) {
                tmp = root->left;
                while(tmp->right != nullptr && tmp->right != root)
                    tmp = tmp->right;
                if(tmp->right != root) {
                    tmp->right = root;
                    root = root->left;
                }else {
                    tmp->right = nullptr;
                    if(p1 == nullptr && pre->val > root->val)
                        p1 = pre;
                    if(p1 != nullptr && pre->val > root->val)
                        p2 = root;
                    pre = root;
                    root = root->right;
                }
            }else {
                if(p1 == nullptr && pre->val > root->val)
                    p1 = pre;
                if(p1 != nullptr && pre->val > root->val)
                    p2 = root;
                pre = root;
                root = root->right;
            }
        }
    }
    void recoverTree(TreeNode* root) {
        pre = new TreeNode(INT_MIN);
        solve(root);
        swap(p1->val,p2->val);
    }
private:
    TreeNode *p1,*p2,*pre,*tmp;
};