[Leetcode][python]Recover Binary Search Tree/恢复二叉搜索树
[Leetcode][python]Recover Binary Search Tree/恢复二叉搜索树
蛮三刀酱
发布于 2019-03-26 17:03:12
发布于 2019-03-26 17:03:12
题目大意
一颗二叉查找树中的某两个节点被错误的交换了，需要恢复成原来的正确的二叉查找树。
挑战：是要求空间复杂度为常数空间。空间复杂度为O(N)是常规解法。
解题思路
来自：博客
算法一： 思路很简单，一颗二叉查找树的中序遍历应该是升序的，而两个节点被交换了，那么对这个错误的二叉查找树中序遍历，肯定不是升序的。那我们只需把顺序恢复过来然后进行重新赋值就可以了。（可针对任意个数目的节点错乱的情况）
算法二： 该算法依然是O(n)空间复杂度，其博客说法有误。 使用了一个prev指针。例如一颗被破坏的二叉查找树如下：
4
/ \
2 6
/ \ / \
1 5 3 7很明显3和5颠倒了。那么在中序遍历时：当碰到第一个逆序时：为5->4，那么将n1指向5，n2指向4，注意，此时n1已经确定下来了。然后prev和root一直向后遍历，直到碰到第二个逆序时：4->3，此时将n2指向3，那么n1和n2都已经确定，只需要交换节点的值即可。prev指针用来比较中序遍历中相邻两个值的大小关系。
算法三： O(1)空间复杂度解法网上有很多，比较难理解，有空深入，这里列举我看到的一种 这道题的真正符合要求的解法应该用的Morris遍历，这是一种非递归且不使用栈，空间复杂度为O(1)的遍历方法，可参见我之前的博客Binary Tree Inorder Traversal 二叉树的中序遍历，在其基础上做些修改，加入first, second和parent指针，来比较当前节点值和中序遍历的前一节点值的大小，跟上面递归算法的思路相似。
代码
算法一
思路太明确但是太笨，在此不贴代码，我认为可以忽略。
算法二
class Solution(object):
def FindTwoNodes(self, root):
if root:
self.FindTwoNodes(root.left)
if self.prev and self.prev.val > root.val:
self.n2 = root
if not self.n1:
self.n1 = self.prev
self.prev = root
self.FindTwoNodes(root.right)
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.n1 = self.n2 = None
self.prev = None
self.FindTwoNodes(root)
self.n1.val, self.n2.val = self.n2.val, self.n1.val算法三（Java）
class Solution {
public:
void recoverTree(TreeNode *root) {
TreeNode *first = NULL, *second = NULL, *parent = NULL;
TreeNode *cur, *pre;
cur = root;
while (cur) {
if (!cur->left) {
if (parent && parent->val > cur->val) {
if (!first) first = parent;
second = cur;
}
parent = cur;
cur = cur->right;
} else {
pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
if (parent->val > cur->val) {
if (!first) first = parent;
second = cur;
}
parent = cur;
cur = cur->right;
}
}
}
if (first && second) swap(first->val, second->val);
}
};总结
这道题暂时先学会算法二足够，之后再深入。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年08月02日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录