给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
示例 1:
输入：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]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0 输出: []
有以下五种情况：
第一种情况：没找到删除的节点，遍历到空节点直接返回了。
第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点。
第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点。
第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点。
第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
比较难理解的是第五种情况，为什么是放在删除节点的右子树的最左面节点的左孩子上呢，我一开始想的是放到删除节点的右子树的最右面节点的左孩子上，这样最右边节点肯定大于删除节点的左子树头节点。
但这样想是错误的，因为二叉搜索树规定了，任一节点的左子树的值必定小于当前节点，所以删除节点的右子树的最左面节点的左孩子是必定大于删除节点的左子树头结点的。
最终代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root==nullptr){
return root;
}//1
if(root->val==key){
if(root->left==nullptr&&root->right==nullptr){
delete root;
return nullptr;
}//2
if(root->left!=nullptr&&root->right==nullptr){
TreeNode* newroot=root->left;
delete root;//释放内存
return newroot;
}//3
if(root->left==nullptr&&root->right!=nullptr){
TreeNode* newroot=root->right;
delete root;//释放内存
return newroot;
}//4
if(root->left!=nullptr&&root->right!=nullptr){
TreeNode* cur=root->right;
TreeNode* oldroot=root;
while(cur->left!=nullptr){
cur=cur->left;
}
cur->left=root->left;
root=root->right;
delete oldroot;//释放内存
return root;
}//5
}
if(root->val>key) root->left=deleteNode(root->left,key);
if(root->val<key) root->right=deleteNode(root->right,key);
return root;
}
};
如果是普通的二叉树，要删除一个节点。
删除的还是中间节点该怎么办呢？应该找那个来补位？
这时候就不能用二叉搜素树的特性了，用交换值的操作来删除目标节点。
代码中目标节点（要删除的节点）被操作了两次：
第一次是和目标节点的右子树最左面节点交换。
第二次直接被NULL覆盖了。
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
if (root->val == key) {
if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用。（如果不是中间节点，第一次就直接删除了）
return root->left;
}
TreeNode *cur = root->right;
while (cur->left) {
cur = cur->left;
}
swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
}
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};
再看一道和删除很相似的题：
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
输入：root = [1,0,2], low = 1, high = 2 输出：[1,null,2]
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出：[3,2,null,1]
这道题如果是数组的话，从头到尾遍历数组，取[low,high]范围的即可。
但这是二叉树，如果root->val在[low,high]之外就返回nullptr的话，就会遍历不到删除节点的右子树。
如例二：
其中的0若是返回了nullptr，就遍历不到2和1了。
怎么办呢？
那就当遍历到不在[low,high]范围的节点时，返回其右子树(rightNode)就好了呗。
最后都不用专门去删，让root->left去接应rightNode即可。
最终代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root==nullptr) return root;
if(root->val<low){
TreeNode* rightNode=trimBST(root->right,low,high);
return rightNode;
}
if(root->val>high){
TreeNode* leftNode=trimBST(root->left,low,high);
return leftNode;
}
root->left=trimBST(root->left,low,high);
root->right=trimBST(root->right,low,high);
return root;
}
};
暂无评论