首页 > 代码库 > Leetcode:Recover Binary Search Tree

Leetcode: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?

分析:二叉树的遍历算法可用的场景很多,此题是个很好的例子。BST的一个特点是它的中序遍历是ascending的,所以我们可以通过BST的中序比遍历确定是哪两个元素的值互换,这里要求是constant space,所以很自然想到O(1)空间复杂度的Morris中序遍历。我们用一个pair记录值互换的两个元素,最后交换他们的值即可。代码如下:

class Solution {public:    void recoverTree(TreeNode *root) {        TreeNode *cur = root;        TreeNode *prev = NULL;        pair<TreeNode *, TreeNode *> broken;                while(cur){            if(cur->left == NULL){                detect(broken, prev, cur);                prev = cur;                cur = cur->right;            }else{                TreeNode *node = cur->left;                for(; node->right && node->right != cur; node = node->right);                if(node->right == NULL){                    node->right = cur;                    cur = cur->left;                }else{                    node->right = NULL;                    detect(broken, prev, cur);                    prev = cur;                    cur = cur->right;                }            }        }        swap(broken.first->val, broken.second->val);    }        void detect(pair<TreeNode *, TreeNode *> &broken, TreeNode *prev, TreeNode *cur){        if(prev != NULL && prev->val > cur->val){            if(broken.first == NULL){                broken.first = prev;            }            broken.second = cur;        }    }};

 

Leetcode:Recover Binary Search Tree