二分探索木におけるノードの削除

    # 二分木のノードを表すクラス
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

    # 二分探索木rootからkeyの値を持つノードを削除する
    def deleteNode(self, root, key):
        if root is None:
            return None

        if key < root.val:
            # 削除対象が自身より小さければ、左部分木から削除する
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            # 削除対象が自身より大きければ、右部分木から削除する
            root.right = self.deleteNode(root.right, key)
        # 削除対象が自身と等しければ、自身を削除する
        else:
            # 子を持たない場合、自身をnullで置き換える
            if root.left is None and root.right is None:
                root = None
            # 1つの子を持つ場合、自身をその子で置き換える
            elif root.left is None or root.right is None:
                root = root.left or root.right            
            else:
                # 2つの子を持つ場合、自身をそのsuccessorの値で上書きし、元のsuccessorを削除する
                root.val = self.successor(root)
                root.right = self.deleteNode(root.right, root.val)

        return root

    # nodeの右部分木からsuccessorの値を返す
    def successor(self, node):
        node = node.right
        while node.left:
            node = node.left
        return node.val