这题要注意一种特殊情况，就是交换的两个数相邻时会怎么样。

此外，题目中要求用O(1)空间解题，那就只能递归中序遍历二叉树了，不能用栈。

1 class Solution { 2     TreeNode* p1; 3     TreeNode* p2; 4     stack
     
       is; 5 public: 6     void inorder(TreeNode* root) 7     { 8         if(root==NULL) 9             return;10         inorder(root->left);11         if(p1==NULL)12         {13             p1=root;14         }15         else if(p1->val>root->val)16         {17             if(is.empty())18             {19                 is.push(p1);20                 is.push(root);21             }22             else23                 is.push(root);24             p1=root;25         }26         else if(p1->val<=root->val)27         {28             p1=root;29         }30         inorder(root->right);31     }32     void recoverTree(TreeNode* root) {33         if(root==NULL||(root->left==NULL&&root->right==NULL))34             return;35         p1=NULL;36         p2=NULL;37         TreeNode* head=root;38         inorder(root->left);39         if(p1==NULL)40         {41             p1=root;42         }43         else if(p1->val>root->val)44         {45             if(is.empty())46             {47                 is.push(p1);48                 is.push(root);49             }50             else51                 is.push(root);52             p1=root;53         }54         else if(p1->val<=root->val)55         {56             p1=root;57         }58         inorder(root->right);59         p2=is.top();60         is.pop();61         p1=is.top();62         is.pop();63         if(is.empty())64         {65             swap(p1->val,p2->val);66         }67         else68         {69             p1=is.top();70             swap(p1->val,p2->val);71         }72         73     }74 };