delete-node-in-a-bst

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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:

<ol>
	<li>Search for a node to remove.</li>
	<li>If the node is found, delete the node.</li>
</ol>

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/04/del_node_1.jpg" style="width: 800px; height: 214px;" />
<pre>
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&#39;s also accepted.
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/04/del_node_supp.jpg" style="width: 350px; height: 255px;" />
</pre>

Example 2:

<pre>
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.
</pre>

Example 3:

<pre>
Input: root = [], key = 0
Output: []
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[0, 104]</code>.</li>
	<li><code>-105 &lt;= Node.val &lt;= 105</code></li>
	<li>Each node has a unique value.</li>
	<li><code>root</code> is a valid binary search tree.</li>
	<li><code>-105 &lt;= key &lt;= 105</code></li>
</ul>

&nbsp;
Follow up: Could you solve it with time complexity <code>O(height of tree)</code>?

deleteNode

Delete Node in a BST

Split BST

split-bst

拆分二叉搜索树

Tree

Binary Search Tree

Binary Tree

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的&nbsp;key&nbsp;对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

<ol>
	<li>首先找到需要删除的节点；</li>
	<li>如果找到了，删除它。</li>
</ol>

&nbsp;

示例 1:

<img src="https://assets.leetcode.com/uploads/2020/09/04/del_node_1.jpg" style="width: 800px;" />

<pre>
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

<img src="https://assets.leetcode.com/uploads/2020/09/04/del_node_supp.jpg" style="width: 350px;" />
</pre>

示例 2:

<pre>
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
</pre>

示例 3:

<pre>
输入: root = [], key = 0
输出: []</pre>

&nbsp;

提示:

<ul>
	<li>节点数的范围&nbsp;<code>[0, 104]</code>.</li>
	<li><code>-105&nbsp;&lt;= Node.val &lt;= 105</code></li>
	<li>节点值唯一</li>
	<li><code>root</code>&nbsp;是合法的二叉搜索树</li>
	<li><code>-105&nbsp;&lt;= key &lt;= 105</code></li>
</ul>

&nbsp;

进阶： 要求算法时间复杂度为&nbsp;O(h)，h 为树的高度。