@@ -0,0 +1,3091 @@
+%22%22%22%0ADefinition of TreeNode:%0Aclass TreeNode:%0A    def __init__(self, val):%0A        self.val = val%0A        self.left, self.right = None, None%0A%22%22%22%0Aclass Solution:%0A    %22%22%22%0A    @param root: The root of the binary search tree.%0A    @param value: Remove the node with given value.%0A    @return: The root of the binary search tree after removal.%0A    %22%22%22%0A    def removeNode(self, root, value):%0A        # write your code here%0A%0A        # Solution 1%0A        # def inorder(bst):%0A        #     if (bst is None):%0A        #         return %5B%5D%0A        #     return inorder(bst.left) + %5Bbst.val%5D + inorder(bst.right)%0A        # def buildTree(li):%0A        #     if (not li):%0A        #         return None%0A        #     mid = len(li) / 2%0A        #     r = TreeNode(li%5Bmid%5D)%0A        #     r.left = buildTree(li%5B:mid%5D)%0A        #     r.right = buildTree(li%5Bmid+1:%5D)%0A        #     return r%0A        # arr = inorder(root)%0A        # if value in arr:%0A        #     i = arr.index(value)%0A        #     arr = arr%5B:i%5D + arr%5Bi+1:%5D%0A        # return buildTree(arr)%0A%0A        # Solution 2%0A        def treeMini(bst):%0A            mini = bst.val%0A            if (bst.left):%0A                mini = treeMini(bst.left)%0A            return mini%0A        parent = None%0A        target = root%0A        dir = None%0A        while (target):%0A            if (target.val %3E value):%0A                parent = target%0A                dir = 'left'%0A                target = target.left%0A            elif (target.val %3C value):%0A                parent = target%0A                dir = 'right'%0A                target = target.right%0A            else:%0A                if (dir is None):%0A                    if (target.left is None and target.right is None):%0A                        return None%0A                    elif (target.left and target.right):%0A                        target.val = treeMini(target.right)%0A                        self.removeNode(target.right, target.val)%0A                    else:%0A                        if (target.left is None):%0A                            return target.right%0A                        else:%0A                            return target.left%0A                else:%0A                    if (target.left is None and target.right is None):%0A                        if (dir == 'left'):%0A                            parent.left = None%0A                        else:%0A                            parent.right = None%0A                    elif (target.left and target.right):%0A                        target.val = treeMini(target.right)%0A                        self.removeNode(target.right, target.val)%0A                    else:%0A                        if (target.left is None):%0A                            if (dir == 'left'):%0A                                parent.left = target.right%0A                            else:%0A                                parent.right = target.right%0A                        else:%0A                            if (dir == 'left'):%0A                                parent.left = target.left%0A                            else:%0A                                parent.right = target.left%0A                break%0A        return root%0A

Add solution to lintcode question 87