首页 > 代码库 > [leetcode]99 Recover Binary Search Tree
[leetcode]99 Recover Binary Search Tree
问题描述：
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?
代码：
void recoverTree(TreeNode *root) {
if(root ==NULL)
return;
bool haveOne = false;
bool isFirst = true;
TreeNode *pre = root;
TreeNode* p = root;
vector<TreeNode*> melement(2);
stack<TreeNode* > myStack;
while(p!=NULL || !myStack.empty())
{
while(p!=NULL){
myStack.push(p);
p = p->left;
}
p = myStack.top();
if(isFirst){
isFirst = false;
pre = p;
}
else {
if(p->val < pre->val){
if(!haveOne){
melement[0] = pre;
melement[1] = p;
haveOne = true;
}
else{
melement[1] = p;
break;
}
}
pre = p;
}
myStack.pop();
p = p->right;
}
int temp = melement[0]->val;
melement[0]->val = melement[1]->val;
melement[1]->val = temp;
return;
}[leetcode]99 Recover Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。