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?
解题思路:
首先理解一下题目的意思，给定一棵BST，其中有两个元素交换了位置，要求恢复这课BST
解题思路仍然是中序遍历，我发现遇到BST的时候，大部分情况下都可以考虑一下中序遍历，由于BST中序遍历的输出是一个有序的数组，因此可以通过比较上一次节点和当前节点找到两个交换的节点，最后交换两个节点的值即可。
代码如下：
class Solution {
public:
void inorderTravel(TreeNode* root, TreeNode* & first, TreeNode* & second, TreeNode* & prev)
{
if(root == NULL) return;
inorderTravel(root->left,first,second,prev);
if(first == NULL && prev != NULL && prev->val > root->val)//注意要保证prev不为空，否则prev->val会越界
first = prev;
if(first != NULL && prev != NULL && prev->val > root->val)
second = root;
prev = root;
inorderTravel(root->right,first,second,prev);
return;
}
void recoverTree(TreeNode* root) {
TreeNode* first = NULL, *second = NULL, *prev = NULL;
inorderTravel(root,first,second,prev);
swap(first->val,second->val);
return;
}
};
