Python O(1) Space and O(n) Solution


  • 0
    Y
    # 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.
            """
            wrongNodes = []
            wrongVals = []
            lastVal = -sys.maxint - 1
            lastElem = None
            node = root
            while node:
              if node.left:
                 prev = node.left
                 while prev.right and prev.right != node:
                     prev = prev.right
                 if prev.right:
                    prev.right = None
                    if lastVal > node.val:
                       wrongNodes.append(lastElem)
                       wrongVals.append(lastElem.val)
                       wrongNodes.append(node)
                       wrongVals.append(node.val)
                    lastVal = node.val
                    lastElem = node
                    node = node.right
                 else:
                    prev.right = node
                    node = node.left
              else:
                if lastVal > node.val:
                   wrongNodes.append(lastElem)
                   wrongVals.append(lastElem.val)
                   wrongNodes.append(node)
                   wrongVals.append(node.val)
                lastVal = node.val
                lastElem = node   
                node = node.right
            wrongVals.sort() 
            n = len(wrongVals)
            for i in range(n):
                wrongNodes[i].val = wrongVals[i]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.