阅读量:0
前言
记录 五十八【701.二叉搜索树中的插入操作】保证插的新节点在叶子节点的位置，如此实现递归。
那么【450.删除二叉搜索树中的节点】删除如何实现？还有简单的方法吗？
一、题目阅读
给定一个二叉搜索树的根节点 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 输出: [] 提示:
节点数的范围 [0, 10^4]. -10^5 <= Node.val <= 10^5 节点值唯一 root 是合法的二叉搜索树 -10^5 <= key <= 10^5 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
二、尝试实现
思路
- 题干告诉说：先找到目标；然后操作删除。
- 找目标：因为是二叉搜索树，利用大小关系的指向，可以向左或向右。即可找到目标；
- 删除操作：本题删除的节点可能不是叶子节点，可能有左子树或右子树。所以，比添加复杂一点。**将删除节点的左子树缀到右子树的合适位置，并将右子树返回上一层，**这样可以保证仍是二叉搜索树。（比如示意一的第一个正确答案）
- 递归函数参数：TreeNode* 当前节点。int key要删除的目标；
- 递归函数返回值：TreeNode* 类型。
- 终止条件：
- 如果是空，说明在树中没有找到要删除的目标，向上返回nullptr。最后返回原树：示例2.
- 如果找到目标：将左子树缀到右子树的合适位置，并将右子树返回上一层。
- 如果删除节点没有右子树，直接返回左子树；
- 如果有右子树，将左子树实现添加操作：如记录 五十八【701.二叉搜索树中的插入操作】缀到右子树
- 中间逻辑：向左或向右找删除目标对象。
代码实现【递归】
class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(!root) return nullptr; if(root->val == key){ if(!root->right) { TreeNode* left = root->left; delete root; return left; }else if(root->right){ if(!root->left) return root->right; TreeNode* temp =root->right; TreeNode* temppre = nullptr; while(temp){ temppre = temp; if(temp->val > root->left->val){ temp = temp->left; }else if(temp->val < root->left->val){ temp = temp->right; } } if(temppre->val > root->left->val) temppre->left = root->left; else temppre->right = root->left; TreeNode* right = root->right; delete root; return right; } } if(root->val > key){ root->left = deleteNode(root->left,key); }else if(root->val < key){ root->right = deleteNode(root->right,key); } return root; } }; 总结：上面代码在找到删除目标之后，处理左右子树用到记录 五十八【701.二叉搜索树中的插入操作】中的迭代法。
三、参考学习
学习内容
- 思路分析：分5种情况——
- 没找到要删的节点；
- 要删除的是叶子节点，左子树空，右子树空；
- 删除目标不是叶子节点，左子树不空，右子树空；可以让父节点直接指向左子树。
- 删除目标不是叶子节点，左子树空，右子树不空；可以让父节点直接指向右子树。
- 删除目标不是叶子节点，左子树不空，右子树不空；调整（复杂点）。让右子树继位，左子树放到右子树中。指明放到右子树的最左下角的位置。
- 总结：思路和二、中分析的一致。
- 代码实现，对比参考代码：
左右子树都不为空。指明放到右子树的最左下角的位置，不用当成添加操作。要简单些。
TreeNode* cur = root->right; // 找右子树最左面的节点 while(cur->left != nullptr) { cur = cur->left; } cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置 TreeNode* tmp = root; // 把root节点保存一下，下面来删除 root = root->right; // 返回旧root的右孩子作为新root delete tmp; // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧） return root;
- 介绍了普通二叉树的删除方式。思路：将要删除的节点换到一个叶子节点的位置。等遍历整个树，遇到这个叶子节点的位置，用空代替，就完成删除操作。参考给了：右子树的最左端，可能一次交换无法把删除目标换到叶子节点的位置，但是继续交换，总能换到，自然最右端也可以。
- 进一步思考普通二叉树的5中情况：
- 没有删除目标，遍历整个树之后，遇到空return nullptr。返回是原来的树；
- 删除目标是叶子节点，左空，右空。return nullptr，上一层直接指向左子树。
- 删除目标不是叶子节点，左不空，右空，可以直接返回左子树，上一层直接指向左子树。
- 删除目标不是叶子节点，左空，右不空，可以在右子树中找一个叶子节点返回。交换就是多步换到叶子节点。
- 删除目标不是叶子节点，左不空，右不空，同第四点。
- 普通二叉树的删除，代码实现【递归】：
class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(!root) return nullptr; if(root->val == key){//找到目标 if(!root->right) {//没有右子树。 TreeNode* left = root->left; delete root; return left;//这里向上返回才能删除目标。 }else if(root->right){ TreeNode* right = root->right; while(right->left){//左子树存在,直到左子树不存在 right = right->left; } swap(root->val,right->val); //这里没有return ，因为还没删掉目标。 } } root->left = deleteNode(root->left); root->right = deleteNode(root->right); return root; } }; 总结
【450.删除二叉搜索树中的节点】和【删除普通二叉树的节点】
（欢迎指正，转载标明出处）
