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，其中有兩個元素交換了位置，要求恢復(fù)這課BST
解題思路仍然是中序遍歷伞租，我發(fā)現(xiàn)遇到BST的時候锭碳，大部分情況下都可以考慮一下中序遍歷弟孟，由于BST中序遍歷的輸出是一個有序的數(shù)組哎壳，因此可以通過比較上一次節(jié)點和當(dāng)前節(jié)點找到兩個交換的節(jié)點扎酷，最后交換兩個節(jié)點的值即可。
代碼如下：
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;
}
};
