450. Delete Node in a BST

🟠   🔖  树 二叉搜索树 二叉树  🔗 LeetCode

题目

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:

1. Search for a node to remove.
2. 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].
• -10^5 <= Node.val <= 10^5
• Each node has a unique value.
• root is a valid binary search tree.
• -10^5 <= key <= 10^5

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

题目大意

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

解题思路

删除一个节点，需要分几种情况讨论：

1. 如果节点是叶子节点（没有左子树和右子树），直接删除即可。
2. 如果节点只有一个子节点，将该节点替换为其子节点。
3. 如果节点有两个子节点，找到右子树中的最小值节点，用该节点的值替换要删除的节点的值，然后递归地删除右子树中的最小值节点。

代码

/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
  if (!root) return null;
  if (root.val > key) {
    root.left = deleteNode(root.left, key);
  } else if (root.val < key) {
    root.right = deleteNode(root.right, key);
  } else {
    if (!root.left) return root.right;
    if (!root.right) return root.left;
    const rightMin = findMin(root.right);
    root.val = rightMin.val;
    root.right = deleteNode(root.right, rightMin.val);
  }
  return root;
};

var findMin = function (root) {
  while (root.left) {
    root = root.left;
  }
  return root;
};

相关题目

相关题目

• 🔒 Split BST

- [🔒 Split BST](https://leetcode.com/problems/split-bst)