首页 > 代码库 > 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。