圖論進階題: 在二元搜索樹BST中刪除節點_Leetcode #450_Leetcode 精選75題

Justin Cron on Unsplash

題目敘述

題目會給我們一棵BST二元搜索樹的根結點root，還有一個指定的目標值key。

要求我們在樹中刪除帶有這個key值的節點，並且返回更新過後二元搜索樹的樹根root。

題目的原文敘述

測試範例

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: 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 above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

約束條件

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].

節點總數目介於0~ 一萬。

請留意邊界條件的處理，題目有可能會給我們一棵空樹喔！

• -10^5 <= Node.val <= 10^5

節點值都介於 負十萬~正十萬 之間。

• Each node has a unique value.

每個節點值都是獨一無二的，不會彼此重複。

• root is a valid binary search tree.

root 是這棵合法二元搜索樹的樹根。

• -10^5 <= key <= 10^5

被刪除的目標值介於 負十萬 ~ 正十萬 之間。

演算法 依照二元搜索樹BST定義的即可