1. # Definition for a binary tree node.
    2. # class TreeNode:
    3. #     def __init__(self, val=0, left=None, right=None):
    4. #         self.val = val
    5. #         self.left = left
    6. #         self.right = right
    7. class Solution:
    8.     def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
    9.         #1. find 2. delete
    10.         if key == None:
    11.             return root
    12.         DummyNode = TreeNode()
    13.         DummyNode.left = root
    14.         targetParent = DummyNode
    15.         while root != None and root.val != key:
    16.             targetParent = root
    17.             if root.val > key:
    18.                 root = root.left
    19.             else:
    20.                 root = root.right
    21.         if root == None:
    22.             return DummyNode.left
    24.         if root.left == None:
    25.             if targetParent.left == root:
    26.                 targetParent.left = root.right
    27.             else:
    28.                 targetParent.right = root.right
    29.         else:       
    30.             maxNode = root.left
    31.             maxNodeParent = root
    32.             while maxNode.right != None:
    33.                 maxNodeParent = maxNode
    34.                 maxNode = maxNode.right
    35.             if maxNodeParent.left == maxNode:
    36.                 maxNode.right = root.right
    37.             else:
    38.                 maxNodeParent.right = maxNode.left
    39.                 maxNode.left = root.left
    40.                 maxNode.right = root.right
    43.             if targetParent.left == root:
    44.                 targetParent.left = maxNode
    45.             else:
    46.                 targetParent.right = maxNode
    48.         return DummyNode.left