跳至主要內容

450. 删除二叉搜索树中的节点


450. 删除二叉搜索树中的节点open in new window

🟠   🔖  二叉搜索树 二叉树  🔗 力扣open in new window LeetCodeopen in new window

题目

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, 10^4].
  • -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;
};

相关题目

题号标题题解标签难度
776拆分二叉搜索树 🔒open in new window 二叉搜索树 递归 1+