第24天。
今天的题目是 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).
Example:
水题,只要先在BST
上做搜索,然后删除就好了,因为只是BST
,所以可以不考虑平衡的问题:
left
和right
都为空:直接删除,返回nullptr
即可left
和right
都不为空:默认采用把右子树的节点拉上来的方式,即把左子树插入到右子树中,然后再返回right
即可。left
和right
有一个不为空,则返回不为空的子树即可。
则代码如下: