题目
给定一个二叉搜索树的根节点root
和一个值key
,删除二叉搜索树中的key
对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
示例1
- 输入:root = [5,3,6,2,4,null,7], key = 3
- 输出:[5,4,6,2,null,null,7]
- 解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它
图示
示例2- 输入: root = [5,3,6,2,4,null,7], key = 0
- 输出: [5,3,6,2,4,null,7]
- 解释: 二叉树不包含值为 0 的节点
示例3- 输入: root = [], key = 0
- 输出: []
思路
删除结点可能出现的五种情况
- 没有找到
key
对应结点:- 没找到删除的节点,遍历到空节点直接返回了
- 找到
key
对应的结点:key
对应结点的左孩子为null
,右孩子不为null
,则直接返回右孩子key
对应结点的右孩子为null
,左孩子不为null
,则直接返回左孩子- 删除结点的右孩子为
null
,左孩子不为null
,删除结点,左孩子补位,返回左孩子为根结点 - 删除结点的左右孩子结点都不为空,则将删除结点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。
注意:因为该题所提供的二叉树为搜索二叉树,即删除结点的左子树值皆小于右子树的值,即可将待删结点的左子树置于待删结点的右子树的左叶子结点下。
代码实现
1 | class Solution { |