My two Python solutions. Recursive O(logN), iterative O(1) space


  • 0
    A
    def recover_tree_recursive(self, node):
        if not node:
            return
    
        def helper(root, prev, l):
            if root.left:
                prev = helper(root.left, prev, l)
            if prev and prev.val > root.val:
                if len(l) == 0:
                    l.append(prev)
                    l.append(root)
                else:
                    l[1] = root
            prev = root
            if root.right:
                prev = helper(root.right, prev, l)
            return prev
    
        p = list()
        helper(node, None, p)
        if len(p) != 0:
            p[0].val, p[1].val = p[1].val, p[0].val
    
    
    def recover_tree_iterative(self, root):
        prev = None
        first = None
        second = None
        while root:
            if root.left:
                buf = root.left
                while buf.right != root and buf.right:
                    buf = buf.right
                if buf.right:
                    buf.right = root
                    root = root.left
                else:
                    if prev and prev.val > root.val:
                        if not first:
                            first = prev
                        second = root
                    prev = root
                    buf.right = None
                    root = root.right
            else:
                if prev and prev.val > root.val:
                    if not first:
                        first = prev
                    second = root
                prev = root
                root = root.right
    
        if first:
            first.val, second.val = second.val, first.val

  • 0
    H

    for the recursive, the space should still be O(n). Think about a tree where each node only has left child, and it will look like a LinkedList


Log in to reply
 

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