题目描述
题目链接:450. Delete Node in a BST
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).
例子
root = [5,3,6,2,4,null,7]
key = 3

Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

Another valid answer is [5,2,6,null,4,null,7].

解题思路
有关于树的问题用递归的方式都比较好解决,针对这道题我们需要删除指定节点。最简单的方法是:首先通过二叉搜索树的性质找出该节点,然后分以下情况讨论:
- 该节点为子节点,没有任何子树,直接删除即可
- 该节点只有一子树(左/右子树),将该节点换成不为空的子树根即可
- 该节点有两子树,我们可以选择将该节点的值换成左子树最大值/右子树最小值,然后删除被替换的节点即可。由于左子树最大节点肯定没有右分支;右子树最小节点肯定没有左分支,所以会回到前一种情况。
代码如下:
1 | class Solution { |
- 时间复杂度: O(n)
- 空间复杂度: O(k) — 树最大深度