题目

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?

题解

最简单的办法，中序遍历二叉树生成序列，然后对序列中排序错误的进行调整。最后再进行一次赋值操作。 但这种方法要求n的空间复杂度，题目中要求空间复杂度为常数，所以需要换一种方法。 递归中序遍历二叉树，设置一个pre指针，记录当前节点中序遍历时的前节点，如果当前节点大于pre节点的值，说明需要调整次序。

代码

class Solution { public: TreeNode *mis1, *mis2; TreeNode *pre; void gao( TreeNode *root ){ if( root == NULL ) return; if( root->left != NULL ){ gao( root->left ); } if( pre != NULL && root->val < pre->val ){ if( mis1 == NULL ){ mis1 = pre; mis2 = root; }else{ mis2 = root; } } pre = root; if( root->right != NULL ){ gao( root->right ); } } void recoverTree(TreeNode* root) { mis1 = mis2 = NULL; pre = NULL; gao( root ); if( mis1 != NULL && mis2 != NULL ){ int tmp = mis1->val; mis1->val = mis2->val; mis2->val = tmp; } } };