450_删除二叉搜索树中的节点

类型：树

• 450. 删除二叉搜索树中的节点 💛 ⭐

  https://leetcode-cn.com/problems/delete-node-in-a-bst/

  ❓ 删除二叉搜索树中值为 key 的结点，要求保证二叉树的性质不变。

  💡 递归

  有三种可能情况：

  • 被删除结点拥有右子树，此时我们从右子树中找到最小结点顶替它。
  • 被删除结点没有右子树，但有左子树，我们直接用左子树（的根结点）顶替它。
  • 被删除结点为叶子结点，可以直接删除。从代码层面来说，可以和上一种情况的处理合并在一起。

  class Solution:
      def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
          if not root:
              return None
  
          # 首先要查找结点
          dummyRoot = TreeNode()
          dummyRoot.left = root
  
          def doDelete(node, key):
              if not node:
                  return None
  
              if key < node.val:
                  node.left = doDelete(node.left, key)
              elif key > node.val:
                  node.right = doDelete(node.right, key)
  
              if node.val == key:
                  if not node.right:
                      return node.left
  
                  # 找到右子树中的最小结点（在右子树中一路往左）
                  parentNode = node
                  childNode = node.right
                  while childNode.left:
                      parentNode = childNode
                      childNode = childNode.left
                  if childNode == parentNode.left:
                      parentNode.left = childNode.right
                  else:
                      parentNode.right = childNode.right
  
                  # 用右子树的最小结点顶替被删结点
                  childNode.left = node.left
                  childNode.right = node.right
                  return childNode
              else:
                  return node
  
          dummyRoot.left = doDelete(dummyRoot.left, key)
          return dummyRoot.left