LeetCode 099 Recover Binary Search Tree

LeetCode 099 Recover Binary Search Tree Problem

Download Code
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    # def recoverTree(self, root):
    #     """
    #     :type root: TreeNode
    #     :rtype: void Do not return anything, modify root in-place instead.
    #     """
    #     # https://discuss.leetcode.com/topic/9305/detail-explain-about-how-morris-traversal-finds-two-incorrect-pointer/2
    #     pre = first = second = None
    #     while root is not None:
    #         if root.left is not None:
    #             temp = root.left
    #             while temp.right is not None and temp.right != root:
    #                 temp = temp.right
    #             if temp.right is not None:
    #                 if pre is not None and pre.val > root.val:
    #                     if first is None:
    #                         first = pre
    #                     second = root
    #                 pre = root
    #                 temp.right = None
    #                 root = root.right
    #             else:
    #                 temp.right = root
    #                 root = root.left
    #         else:
    #             if pre is not None and pre.val > root.val:
    #                 if first is None:
    #                     first = pre
    #                 second = root
    #             pre = root
    #             root = root.right
    #     # only two elements are swapped
    #     if first is not None and second is not None:
    #         first.val, second.val = second.val, first.val


    # https://discuss.leetcode.com/topic/3988/no-fancy-algorithm-just-simple-and-powerful-in-order-traversal/2
    def __init__(self):
        self.first = self.second = None
        self.pre = TreeNode(-sys.maxint - 1)


    def recoverTree(self, root):
        self.traverse(root)
        self.first.val, self.second.val = self.second.val, self.first.val

    def traverse(self, root):
        if root is None:
            return
        self.traverse(root.left)
        if self.pre.val >= root.val:
            if self.first is None:
                self.first = self.pre
            if self.first is not None:
                self.second = root
        self.pre = root
        self.traverse(root.right)



Download Recover Binary Search Tree.py

List of all Recover Binary Search Tree problems

Leetcode 099 Recover Binary Search Tree problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

self.val = x

Feedback is the most important part of any website.

If you have any query, suggestion or feedback, Please feel free to contact us.