[LeetCode] 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.

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, 104].
-105 <= Node.val <= 105
Each node has a unique value.
root is a valid binary search tree.
-105 <= key <= 105

Follow up: Could you solve it with time complexity O(height of tree)?

删除二叉搜索树中的节点。

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

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

首先找到需要删除的节点；
如果找到了，删除它。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

因为是BST，所以找节点和删除节点还是有一定规律可循的。首先，找到要删除的节点不难，如果 root.val < key 就往右走；如果 root.val > key 就往左走，直到找到要删除的节点。接下来就要考虑删除节点的情况了：

1. 如果要删除的节点没有左子树或者右子树，说明他是一个叶子节点，直接返回 null 即可。
2. 如果要删除的节点只有左子树，那就把他的左孩子的值赋给他，然后去左子树里删除这个节点。这就相当于是把这个节点的值替换成了他的左孩子的值。
3. 如果要删除的节点只有右子树，那就把他的右孩子的值赋给他，然后去右子树里删除这个节点。这就相当于是把这个节点的值替换成了他的右孩子的值。
4. 如果要删除的节点有左右子树，那就要找到右子树中最小的节点，把这个节点的值赋给要删除的节点，然后去右子树里删除这个最小的节点。这样就相当于是把这个节点的值替换成了他的右孩子的最小值。

复杂度

时间O(n)
空间O(n)

代码

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // corner case
		if (root == null) {
			return null;
		}

		// normal case
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            // 找到要删除的节点
            if (root.left == null) {
				return root.right;
			}
            if (root.right == null) {
				return root.left;
			}

            // 找到右子树最小值节点
            TreeNode minNode = getMin(root.right);
            root.val = minNode.val;
            // 删除右子树中的最小节点
            root.right = deleteNode(root.right, minNode.val);
        }
        return root;
    }

    // 获取以 node 为根的子树中的最小节点
    private TreeNode getMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}