**一. 題目描述** Two elements of a binary search tree (BST) are swapped by mistake.? Recover the tree without changing its structure.? Note:? A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? **二. 題目分析** 題目的大意是，在二叉排序樹中有兩個節點被交換了，要求把樹恢復成二叉排序樹。 一個最簡單的辦法是，中序遍歷二叉樹生成序列，然后對序列中排序錯誤的進行調整。最后再進行一次賦值操作。這種方法的空間復雜度為`O(n)`。 但是，題目中要求空間復雜度為常數，所以需要換一種方法。 遞歸中序遍歷二叉樹，設置一個`prev`指針，記錄當前節點中序遍歷時的前節點，如果當前節點大于`prev`節點的值，說明需要調整次序。 **三. 示例代碼** ~~~ /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *p,*q; TreeNode *prev; void recoverTree(TreeNode *root) { p=q=prev=NULL; inorder(root); swap(p->val,q->val); } void inorder(TreeNode *root) { if(root->left)inorder(root->left); if(prev!=NULL&&(prev->val>root->val)) { if(p==NULL)p=prev; q=root; } prev=root; if(root->right)inorder(root->right); } }; ~~~ **四. 小結** 有一個技巧是，若遍歷整個序列過程中只出現了一次次序錯誤，說明就是這兩個相鄰節點需要被交換。如果出現了兩次次序錯誤，那就需要交換這兩個節點。