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?

URL: https://leetcode.com/problems/recover-binary-search-tree/

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.__prev = None
        self.__node1 = None
        self.__node2 = None

    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.recoverTreeHelp(root) 
        temp = self.__node1.val
        self.__node1.val = self.__node2.val
        self.__node2.val = temp

    def recoverTreeHelp(self, root):
        if root == None:
            return None

        self.recoverTreeHelp(root.left)
        if self.__prev != None:
            if self.__prev.val > root.val:
                if self.__node1 == None:
                    self.__node1 = self.__prev
                self.__node2 = root
        self.__prev = root
        self.recoverTreeHelp(root.right)

results matching ""

    No results matching ""