LeetCode 99. 恢复二叉搜索树(morris)
原题链接
困难
作者:
tom233
,
2021-02-02 21:54:45
,
所有人可见
,
阅读 508
morris算法:常数空间复杂度、线性时间复杂度遍历一颗二叉树
思路:
1.当前节点没有左孩子,输出当前左孩子,然后进入右孩子
2.当前节点有左孩子,寻找当前节点的前驱(进入左孩子,然后一直往右)
2.1.如果前驱是当前节点自己,说明当前节点的左子树全部已遍历。将前驱的右孩子恢复为空,进入右子树
2.2.如果前驱的右孩子为空,说明当前节点左子树没有遍历,进入左子树。同时前驱的右孩子指向当前节点,方便回溯
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *first = NULL, *second, *prep = NULL;
while(root)
{
if(!root->left)
{
if(prep && prep->val >= root->val)
{
if(!first)first = prep, second = root;
else second = root;
}
prep = root;
root = root->right;
}
else
{
TreeNode *p = root->left;
while(p->right && p->right != root)p = p->right;
if(!p->right)
{
p->right = root;
root = root->left;
}
else
{
p->right = NULL;
if(prep && prep->val >= root->val)
{
if(!first)first = prep, second = root;
else second = root;
}
prep = root;
root = root->right;
}
}
}
swap(first->val, second->val);
}
};