99. Recover Binary Search Tree
problem description
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?
algorithm thought
已知BST中有两个数字是错的,那么我们就找到两个错的位置就行。还是中序遍历,找到不是顺序增长的两个位置。记录下来,最后交换两个的值
code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* first=NULL;
TreeNode* second=NULL;
int count=0;
TreeNode* pre=new TreeNode(INT_MIN);
void recoverTree(TreeNode* root) {
bool bo=false;
travers(root);
int tmp=first->val;
first->val=second->val;
second->val=tmp;
}
void travers(TreeNode* root){
if(count==2||root==NULL)
return;
travers(root->left);
if(first==NULL&&pre->val>root->val){
first=pre;
}
if(first!=NULL&&pre->val>root->val){
second=root;
count++;
}
pre=root;
travers(root->right);
}
};
//利用bst的中序遍历性质来解决问题
algorithm analysis
一次遍历,时间复杂度O(n)
Last updated