99. Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2]
1
/
3
\
2
Output: [3,1,null,null,2]
3
/
1
\
2
Example 2:
Input: [3,1,4,null,null,2]
3
/ \
1 4
/
2
Output: [2,1,4,null,null,3]
2
/ \
1 4
/
3
Follow up:
A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?
题意：二叉搜索树中有两个结点顺序是逆序的，恢复二叉搜索树
思路：只需要找到两个逆序对，交换即可，代码是参照大神的
class Solution{
public:
//firstElement和secondElement分别代表第一个逆序的位置和第二个逆序的位置
//第一步需要在中序遍历序列中找到这两个位置，第二步需要交换这两个位置
TreeNode *firstElement;
TreeNode *secondElement;
TreeNode *preElement;
//代表当前遍历的位置的中序前驱节点，先赋一个最小值
//traverse函数负责找到两个逆序的位置，随后用swap函数将这两个位置进行交换
void recoverTree(TreeNode* root) {
traverse(root);
swap(firstElement->val, secondElement->val);
}
//中序遍历序列找到两个逆序的位置(找到两个逆序对即可)
void traverse(TreeNode *root){
if(root == NULL)
return ;
//中序遍历左子树
traverse(root->left);
if(preElement != NULL){
//查看是否逆序，如果逆序，给firstElement和secondElement赋值
if(firstElement == NULL && preElement->val > root->val){
//当firstElement还没有被赋值，第一个逆序位置是pre节点
firstElement = preElement;
}
if(firstElement != NULL && preElement->val > root->val){
//当firstElement已经被赋值，第二个逆序位置是root节点
secondElement = root;
}
}
preElement = root; //更新preElement的值
// cout<<preElement->val;
//中序遍历右子树
traverse(root->right);
}
};
