450. Delete Node in a BST BST的删除

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        p = root
        pp = None
        while p and p.val!=key:
            if p.val > key:
                pp = p
                p = p.left
            else:
                pp = p
                p = p.right
        if p is None:
            return root
        
        if p.left and p.right:
            minp = p.right
            minpp = p
            while minp.left:
                minpp = minp
                minp = minp.left
            p.val = minp.val
            p = minp
            pp = minpp
            
        if p.left:
            child = p.left
        elif p.right:
            child = p.right
        else:
            child = None
            
        if pp is None:
            root = child
        elif pp.left == p:
            pp.left = child
        else:
            pp.right = child
        return root