0450. 删除二叉搜索树中的节点 #
- 标签:树、二叉搜索树、二叉树
- 难度:中等
题目大意 #
描述:给定一个二叉搜索树的根节点 root
,以及一个值 key
。
要求:从二叉搜索树中删除 key 对应的节点。并保证删除后的树仍是二叉搜索树。要求算法时间复杂度为 $0(h)$,$h$ 为树的高度。最后返回二叉搜索树的根节点。
说明:
- 节点数的范围 $[0, 10^4]$。
- $-10^5 \le Node.val \le 10^5$。
- 节点值唯一。
root
是合法的二叉搜索树。- $-10^5 \le key \le 10^5$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归 #
删除分两个步骤:查找和删除。查找通过递归查找,删除的话需要考虑情况。
- 从根节点
root
开始,递归遍历搜索二叉树。 - 如果当前节点节点为空,返回当前节点。
- 如果当前节点值大于
key
,则去左子树中搜索并删除,此时root.left
也要跟着递归更新,递归完成后返回当前节点。 - 如果当前节点值小于
key
,则去右子树中搜索并删除,此时root.right
也要跟着递归更新,递归完成后返回当前节点。 - 如果当前节点值等于
key
,则该节点就是待删除节点。- 如果当前节点的左子树为空,则删除该节点之后,则右子树代替当前节点位置,返回右子树。
- 如果当前节点的右子树为空,则删除该节点之后,则左子树代替当前节点位置,返回左子树。
- 如果当前节点的左右子树都有,则将左子树转移到右子树最左侧的叶子节点位置上,然后右子树代替当前节点位置。返回右子树。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是二叉搜索树的节点数。
- 空间复杂度:$O(n)$。