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
confused what "{1,#,2,3}" means > read more on how binary tree is serialized on OJ.
题目说一个二叉搜索树的两个节点被错误交换，要求不改变树的结构恢复正常的二叉搜索树。
解法一：
O(n)的空间复杂度的解决办法是比较容易的，我们可以把二叉搜索树按中序遍历赋值到数组中，然后直接扫描数组元素记录逆序的位置，逆序的对数可能有一对，也可能有两对。假设元素按顺序排序是1、2、3、4、5.
一对的情况，如：1、2、4、3、5，这样我们直接交换4和3的值即可。如果是两对的情况，例如1、5、3、4、2，我们查找到逆序位置的元素5和2，交换5和2即可。
但是如何根据这个信息去交换二叉树中的节点呢？我们可以存储元素值与树节点指针的映射，用STL的map容器，key为元素值，value为节点指针。
代码如下：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode *root) {
vector
v;
map
mm; //inorder stack
s; s.push(root); while (!s.empty()) { TreeNode *tmp = s.top(); while (tmp->left!=NULL) { s.push(tmp->left); tmp = tmp->left; } v.push_back(tmp->val); mm[tmp->val] = tmp; s.pop(); while (tmp->right==NULL && !s.empty()) { tmp = s.top(); v.push_back(tmp->val); mm[tmp->val] = tmp; s.pop(); } if (tmp->right!=NULL) s.push(tmp->right); } int p1=-1, p2 = -1; for (int i=1; i
val, mm[v[p1+1]]->val); } else { swap(mm[v[p1]]->val, mm[v[p2+1]]->val); } } private: void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; } };
解法二：
认真考虑二叉搜索树的性质，两个节点值被交换，可能有好几种情况，一是根节点分别是左右子孙的节点值被交换，二是根节点值与左子树一节点值被交换，三是根节点值与右子树一节点被交换，四是左子树或者右子树里面的两个节点被交换。
情况一时，我们可以在左子树中找比根节点值大的节点值，在右子树中找比根节点值小的节点值，然后交换找到的两个节点的值；
情况二时，我们要找到左子树中比根节点值最大的节点，然后交换根节点与找到节点的值；
情况三时，我们要找到右子树中比根节点值最小的节点，然后交换根节点与找到节点的值；
情况四时，我们对根节点的左右子树再递归调用这样的操作。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode *root) {
if (root==NULL)
return;
//找左子树孩子的最大值节点
TreeNode *leftBiggest = root;
find(root->left, leftBiggest, "largest");
//找右子树孩子的最小值节点
TreeNode *rightSmallest = root;
find(root->right, rightSmallest, "smallest");
// root的两个左右子孙误交换了
if (leftBiggest!=root && rightSmallest!=root) {
swap(leftBiggest->val, rightSmallest->val);
} else if(leftBiggest != root) { //右子树正常，root与leftBiggest误交换了
swap(root->val, leftBiggest->val);
} else if (rightSmallest != root) { //左子树正常，root与rightSmallest误交换了
swap(root->val, rightSmallest->val);
} else { // 左子树或右子树里的两个节点误交换
recoverTree(root->left);
recoverTree(root->right);
}
}
private:
void find(TreeNode *root, TreeNode *&p, const string& relation) {
if (root == NULL)
return;
if (relation=="smallest" && root->val
val)
p = root;
else if (relation=="largest" && root->val>p->val)
p = root;
find(root->left, p, relation);
find(root->right, p, relation);
}
void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}
};