0450. Delete Node in a BST¶
题目信息¶
- 题号:
0450
- 难度:
Medium
- 主题:
二叉搜索树、按键删除、结构重连、返回根节点
- 原题:
- 重点:
删除值等于
key的节点、删除后仍满足 BST 性质、键不存在时保持不变、根节点可能改变
题目重述¶
给定二叉搜索树根节点 root 和整数 key,删除树中节点值等于 key 的节点,并返回删除后的根节点。输入树中的节点值互不相同。
若目标节点不存在,返回原树。删除叶节点、只有一个孩子的节点或有两个孩子的节点后,都必须保留其余所有节点,并使结果继续满足二叉搜索树性质。树中节点数位于 [0, 10^4],节点值和 key 位于 [-10^5, 10^5]。
自建示例¶
删除叶节点:
输入:root = [8,3,10,1,6,null,14],key = 14
输出:[8,3,10,1,6]
解释:14 是叶节点,删除它不会改变其他节点的父子关系,结果仍是合法 BST。
目标键不存在:
输入:root = [4,2,7],key = 5
输出:[4,2,7]
解释:树中没有值 5 的节点,因此结构和根节点保持不变。
按 BST 路径查找并处理三种结构¶
先利用 BST 的大小关系递归向左或向右查找 key,没有找到时沿途原样返回。找到目标节点后,叶节点直接返回空;只有一个孩子时返回该孩子,让父节点跳过目标节点;有两个孩子时,用右子树中的最小节点(中序后继)覆盖当前值,再递归删除那个后继节点。
后继节点是右子树最左侧的节点,它大于当前节点且不大于右子树中的其他节点。用它替换后,左子树仍全部更小,右子树仍全部更大,递归删除后继也只会遇到“叶节点或只有一个孩子”的情况。
C++ 实现¶
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr;
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 == nullptr) return root->right;
if (root->right == nullptr) return root->left;
TreeNode* successor = root->right;
while (successor->left != nullptr) {
successor = successor->left;
}
root->val = successor->val;
root->right = deleteNode(root->right, successor->val);
}
return root;
}
};
代码分析¶
递归返回值承担“删除后该子树的新根”,因此目标节点是根、叶节点或只有一个孩子时都能正确接回父节点。双孩子情况只替换值并在右子树中删除重复的后继节点,不会丢失其他子树。时间复杂度为 O(h),其中 h 是树高;递归额外空间为 O(h)。