Leetcode 450. Deleting a node in a binary search tree

link ：https://leetcode.cn/problems/delete-node-in-a-bst/
The addition, deletion, modification and query of binary search tree are necessary contents , But deleting is a little more difficult than other operations , You can practice with this question .

Title Description

Given the root node of a binary search tree root And a value key, Delete the key Corresponding node , And keep the property of binary search tree unchanged . Back to binary search tree （ May be updated ） Reference to the root node of .

The recursive method

class Solution:
    """  The recursive method  """
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        """  Delete root as root Of BST in node.val be equal to key The node of , Returns the deleted root node （ Root node may change ） """
        if not root:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        # # root There may be 0 or 1 A child node , But the treatment is the same , Return to the child node 
        elif not root.left or not root.right:
            child = root.left if root.left else root.right
            return child
        else:
            successor = root.right  #  Use successor nodes instead of root
            while successor.left:
                successor = successor.left
            root.val = successor.val  # root.val Assign values to subsequent nodes 
            root.right = self.deleteNode(root.right, successor.val)
        return root

Iterative method

The basic idea of iterative solution is the same as above , This is to discuss whether the deleted node is the root node in multiple categories .

class Solution:
    """  Non recursive solution  """
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root
        node, father = self.findNode(root, key)
        if not node:
            return root
        return self.delete(root, father, node)

    def delete(self, root, father, node):
        if node.left and node.right:
            suc_father, successor = self.findSuccessor(node)
            node.val = successor.val
            return self.delete(root, suc_father, successor)
        if not node.left and not node.right:
            if root == node:
                return None
            if father.left == node:
                father.left = None
            else:
                father.right = None
            return root
        child = node.left if node.left else node.right
        if root == node:
            return child
        if father.left == node:
            father.left = child
        else:
            father.right = child
        return root

    def findNode(self, root, key):
        if not root:
            return root
        if root.val == key:
            return root, None
        father = root
        while root:
            if root.val == key:
                return root, father
            elif key < root.val:
                father = root
                root = root.left
            else:
                father = root
                root = root.right
        return None, None

    def findSuccessor(self, root):
        successor = root.right
        father = root
        while successor.left:
            father = successor
            successor = successor.left
        return father, successor