<jupyter_start><jupyter_text>说明：    给定BST的根节点引用和key，请在BST中删除具有给定key的节点。    返回BST的根节点引用（可能已更新）。    删除基本上可以分为两个阶段：        1、搜索要删除的节点。        2、如果找到该节点，请删除该节点。注意：    时间复杂度应为O（树的高度）。<jupyter_code>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:
        if not root:
            return root
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
            if not left and not right:
                root = None
            elif not left and right:
                root = root.right
            elif not right and left:
                root = root.left
            else:
                min_root = self.helper(root.right)
                root.val = min_root.val
                root.right = self.deleteNode(root.right, root.val)
        return root
    
    def helper(self, root):
        cur = root
        while root.left:
            cur = root.left
        return cur
                
        else: # Node to delete
            # Case 1: No childs.
            if root.left == None and root.right == None:
                root = None
                
            # Case 2: One child
            elif root.left == None and root.right != None :
                root = root.right
            elif root.right == None and root.left != None :
                root = root.left
                
            # Case 3: 2 children
            else:
                minRoot = self.findMinNode(root.right)
                root.val = minRoot.val
                root.right = self.deleteNode(root.right,root.val)
                
        return root<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0855614973262032, 'fraction_numerical': 0.0037433155080213902, 'mean_word_length': 1.33875, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '389879', 'license': 'Apache-2.0', 'n_tokens_mistral': 592, 'n_tokens_neox': 599, 'n_words': 138, 'path': 'Tree/0831/450. Delete Node in a BST.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '1870'}