python Morris


  • 0
    Z
    class Solution(object):
        a, b, prev = None, None, None
        
        def recoverTree(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            def process_node():
                if self.prev and self.prev.val > root.val:
                    if not self.a:
                        self.a = self.prev
                    self.b = root
                self.prev = root
                
            while root:
                if not root.left:
                    process_node()
                    root = root.right
                else:
                    pred = root.left
                    while pred.right and pred.right is not root:
                        pred = pred.right
                    if not pred.right:
                        pred.right = root
                        root = root.left
                    else:
                        pred.right = None
                        process_node()
                        root = root.right
            if self.a and self.b:
                self.a.val, self.b.val = self.b.val, self.a.val
    

Log in to reply
 

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