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

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution {
public:
voidrecoverTree(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);  
    }
};