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)