代码链接：
https://leetcode.com/problems/recover-binary-search-tree/description/
思路：
找到两个需要交换的节点（first,second），将它们的值交换即可。
根据二叉搜索树的特性，中序遍历序列是一个递增序列（a1<a2<a3<...<an）。
(1)若ai>a(i+1)则ai即为第一个需要交换的节点；
(2)若j>=i && aj>a(j+1)则a(j+1)是第二个需要交换的节点；
(3)交换(ai,a(j+1))。
假设一个有问题的二叉搜索树的中序遍历序列为：
5,2,3,4,1
则5是第一个节点，因为5>2,4>1所以5是第一个，1是第二个需要交换的节点。
方法1：
使用递归的方式：
void InorderTraverse(root){ InorderTraverse(root->left); do_something(root); InorderTraverse(root->right); }由于在递归调用过程中使用了栈，这种方法的空间复杂度是O(n)。
方法2：
使用Morris遍历的方式。
while(root){ if(root->left){ tmp=root->left; while(tmp->right!=NULL && tmp->right!=root) tmp=tmp->right; if(tmp->right){ tmp->right=NULL; do_something(root); root=root->right; } else{ tmp->right=root; root=root->left; } } else{ do_something(root); root=root->right; } }把do_something(root);替换为实际代码即可。
/** * 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 *pt=NULL; TreeNode *first=NULL,*second=NULL,*prev=new TreeNode(INT_MIN); while(root){ if(root->left){ pt=root->left; while(pt->right && pt->right!=root) pt=pt->right; if(pt->right){ pt->right=NULL; if(first==NULL && prev->val > root->val) first=prev; if(first && prev->val > root->val) second=root; prev=root; root=root->right; } else{ pt->right=root; root=root->left; } } else{ if(first==NULL && prev->val > root->val) first=prev; if(first && prev->val > root->val) second=root; prev=root; root=root->right; } } if(first){ int tmp=first->val; first->val=second->val; second->val=tmp; } } };