【Leetcode刷题Python】450. 删除二叉搜索树中的节点

1 题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点； 如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3 输出：[5,4,6,2,null,null,7] 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 另一个正确答案是 [5,2,6,null,4,null,7]。

2 解析

二叉搜索树的题目往往可以用递归来解决。此题要求删除二叉树的节点，函数deleteNode 的输入是二叉树的根节点 root 和一个整数key，输出是删除值为 key 的节点后的二叉树，并保持二叉树的有序性。可以按照以下情况分类讨论：

• root 为空，代表未搜索到值为key的节点，返回空。
• root.val>key，表示值为key 的节点可能存在于root 的左子树中，需要递归地在root.left 调用deleteNode，并返回root。
• root.val Optional[TreeNode]: if not root: return None if root.val >key: root.left = self.deleteNode(root.left,key) elif root.val