Python solution with detailed explanation


  • 1
    G

    Solution

    Recover Binary Search Tree https://leetcode.com/problems/recover-binary-search-tree/?tab=Description

    Algorithm

    1. Use a tree example: [100, 50, 200, 25, 75, 99, 400]
    2. Sorted Order: 25,50,75,100,150,200,400
    3. You can have out of order 50 and 200: 25,200,75,100,150,50,400. Notice in this case we have 2 out of order pairs: (200,75) and (150,50). Simply swap 200 and 50.
    4. What if 25/50 or 200/400 are swapped? In that case we will have just one out of order element.
    5. 3 and 4 give us our algorithm.
    class Solution(object):
        def recoverTree(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            self.order = []
            self.prev = None
            self.inorder(root)
            if len(self.order) == 2:
                self.swap(self.order[0][0], self.order[1][1])
            elif len(self.order) == 1:
                self.swap(self.order[0][0], self.order[0][1])
            return
        
        def inorder(self, root):
            if root == None:
                return
            self.inorder(root.left)
            if self.prev and self.prev.val > root.val:
                self.order.append((self.prev, root))
            self.prev = root
            self.inorder(root.right)
            return
        
        def swap(self, r1, r2):
            r1.val, r2.val = r2.val, r1.val
            return
    

  • 0
    D

    i come up with the same idea and like your explanation. and here is my implementation.

    class Solution(object):
        def recoverTree(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            
            first, second = None, None
            
            stack, node, prev = [], root, None
            while stack or node:
                if node:
                    stack.append(node)
                    node = node.left
                else:
                    node = stack.pop()
                    if prev and prev.val > node.val:
                        if not first and not second:
                            first, second = prev, node
                        else:
                            second = node
                            
                    prev, node = node, node.right
                    
            if first and second:
                first.val, second.val = second.val, first.val
                
    

Log in to reply
 

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