2020-08-16 - 日理万妓 2021-06-10 20:39 194阅读 0赞 BST的删除操作向来被认为难度很大,因为它不同于插入,定位到了那个该插入的位置选择左边/右边进行插入即可,而删除操作则需要分成以下三种情况进行讨论,删除难度从上到下依次递增: * case1 叶子结点 * case2 只有左子树/只有右子树的结点 * case3 左子树和右子树都存在的结点 其实case1,case2的难度系数都不大,重难点就是在于处理case3这种情况的结点 * case1 叶子结点直接将结点删除(树少了ta照样长得很茁壮,没有人会记得一片叶子的存在) * case2 要删除的结点用一个指针进行保存,而自己跳到自己的左/右子树上,即parent牺牲自己抱住了lchild/rchild(孩子在路中央呆若木鸡,眼看着大卡车迎面而来,父亲眼疾手快将孩子推向一边,而让冰冷的钢铁撞击在自己炙热的身躯上,代替了孩子的牺牲) * case3 见下文具体分析 注:以下讲解的代码思路参考于《大话数据结构》 本体代码树结构如下定义: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ 那么下面我们就开始进行整个代码思路的讲解 首先我们给出解BST问题的一个代码框架,我们定义这里删除BST中某个结点的函数为deleteNode(TreeNode\* root, int key),其中TreeNode\* root为已经构造好了的一棵符合规范的BST,而int key则是我们即将要删除的目标 TreeNode* deleteNode(TreeNode* root, int key) { if ( root == nullptr ) return root; if ( key == root->val ) { // 定位到目标进行删除操作... } // 若key小于当前定位到的root->val,则说明root->val应该继续往左走才有机会定位到key else if ( key < root->val ) root->left = deleteNode(root->left, key); // 若key大于当前定位到的root->val,则说明root->val应该往右走才有机会定位到当前key else root->right = deleteNode(root->right, key); } 以上的模版在接BST题时非常有用!完美利用了BST的性质,一定要牢记于心。 剩下的便是今天我们要攻克的难题:删除结点。 ### case1 叶子结点 ### 直接进行删除(直接使用delete删除其实是不严谨,这里我们忽略删除的细节,具体讲解整体思路部分) if ( key == root->val ) { // 定位到目标进行删除操作... // case1 : 叶子结点的删除操作 if ( root->left == nullptr && root->right == nullptr ) delete root; } ### case2 只有左子树/只有右子树的结点 ### 保存这个被删除的结点,把孩子推向一边,有左子树就把孩子推到左边,有右子树就把孩子推到右边 TreeNode* p; TreeNode* q; if ( key == root->val ) { // 定位到目标进行删除操作... // case1 : 叶子结点的删除操作 if ( root->left == nullptr && root->right == nullptr ) delete root; // case2 : 只有左子树/只有右子树的结点 // 重接左子树 if ( root->right == nullptr ) { p = root; root = root->left; delete p; } // 重接右子树 else if ( root->left == nullptr ) { p = root; root = root->right; delete p; } } ### case3 左子树和右子树都存在的结点 ### 在开始讲解最关键的这一部分之前,首先介绍一个BST中直接前驱/直接后继的概念: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NDA2NjU2_size_16_color_FFFFFF_t_70_pic_center] 如果不能理解这个概念,那么我给你一个建议:找一棵普通的树,完完整整的结合中序遍历的代码过一遍遍历的顺序,好好的去理解中序遍历回溯的时机。 在理解了上述概念后,直接后继留给你们去推导。 其次需要注意的是,这里我们所说的直接前驱/后继是数组进行中序遍历时遍历到的当前结点的上一个元素! 好,接着往下讲,我们又知道,BST的中序遍历结果是一个升序数组,但是结合BST的这点性质,可以得出一个结论:BST中某个结点的前驱/后继结点 就是 BST中序遍历得到的已排序数组中前一个/后一个元素。 还是看上面的例子,5的直接前驱结点是4,也是中序遍历得到的排序数组中5的前一个元素,这不是巧合! 奇怪的思路增加了: **狸猫换太子** 这是什么意思呢?不难发现:我们的直接前驱/后继结点所属的情况一定属于case1和case2,即一定为叶子结点or只有左/右子树的结点。假设我们将要删除的结点伪装成其直接前驱/后继结点,再将直接前驱/后继结点删除,神不知鬼不觉的“算法版狸猫换太子”岂不美哉?好,现在我们已经清晰的转化了问题,我们来开始写代码: TreeNode* p; TreeNode* q; if ( key == root->val ) { // 定位到目标进行删除操作... // case1 : 叶子结点的删除操作 if ( root->left == nullptr && root->right == nullptr ) delete root; // case2 : 只有左子树/只有右子树的结点 // 重接左子树 if ( root->right == nullptr ) { p = root; root = root->left; delete p; } // 重接右子树 else if ( root->left == nullptr ) { p = root; root = root->right; delete p; } else { // case3 : 左子树右子树都存在的结点 // 我们首先按伪装成前驱结点来写代码,找到当前结点root的左结点的最右边的结点 q = root->left; while ( q->right ) { q = q->right; } // 狸猫换太子 root->val = q->val; // ... } } 不知道你是否敏感,我们在狸猫换太子之后出现了问题。正如我上面所说,直接前驱结点也是分两种情况的:**i.一种是当前的结点的左结点的最右边的结点 ii.那么如果出现当前结点的左结点没有右子树,则当前结点的左结点就是当前结点的前驱结点**(这段有点套娃,不理解的就去看上面我给出的图)。所以我是如何得知这里的前驱结点属于哪一种情况的呢? 这里又不得不提一个链表问题中常用的思想:用一个指针pre记录之前遍历过的位置。 我们不难发现,假设我们用一个指针p记录指针q上一次遍历到的结点,那么当我对应情况 **i** 时,我的p结点只要继承q结点的“遗产”就好了(下面会具体讲遗产是什么),而对应到情况 **ii** 的时候,q刚到达当前结点的左结点,p根本就没有挪动的必要。不难看出,我们可以用一个指针p在不同情况会处于不同的位置上来区分两种情况。 TreeNode* p; TreeNode* q; if ( key == root->val ) { // 定位到目标进行删除操作... // case1 : 叶子结点的删除操作 if ( root->left == nullptr && root->right == nullptr ) delete root; // case2 : 只有左子树/只有右子树的结点 // 重接左子树 if ( root->right == nullptr ) { p = root; root = root->left; delete p; } // 重接右子树 else if ( root->left == nullptr ) { p = root; root = root->right; delete p; } else { // case3 : 左子树右子树都存在的结点 // 我们首先按伪装成前驱结点来写代码,找到当前结点root的左结点的最右边的结点 // p指向当前结点,q指向当前结点的左结点 p = root; q = root->left; // 假设q有右子树就不断往右推进,p随之跟进,而假设q没有右子树,p和q都滞留在原地 while ( q->right ) { p = q; q = q->right; } // 狸猫换太子,不难理解,我们即将要删除的并不是root,而是q root->val = q->val; // 情况i:直接前驱为当前的结点的左结点的最右边的结点 if ( p != root ) // 直接前驱结点是一定不会存在右子树这一说了,已经推到了最右边,所以左子树是他留给p的遗产(当然如果q是个叶子结点的就是一个穷光蛋,什么都不剩),接到p的右子树上 p->right = q->left; // 情况ii:当前结点的左结点就是当前结点的前驱结点,将遗产接到p的左子树上 else p->left = q->left; delete q; } } 别忘记之前我们所讲的模版,这一部分只是属于if ( key == root->val )这个代码段的,下面附上完整代码,我在基准情形那一块做了点优化,即当树中仅有一个结点且这个结点的val值就是序要删除的值的时候直接返回nullptr: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { TreeNode* p; TreeNode* q; if ( root == nullptr || root->val == key && root->left == nullptr && root->right == nullptr ) return nullptr; else { if ( key == root->val ) { if ( root->left == nullptr && root->right == nullptr ) delete root; if ( root->right == nullptr ) { p = root; root = root->left; delete p; } else if ( root->left == nullptr ) { p = root; root = root->right; delete p; } else { p = root; q = root->left; while ( q->right ) { p = q; q = q->right; } root->val = q->val; if ( p != root ) p->right = q->left; else p->left = q->left; delete q; } } else if ( key < root->val ) root->left = deleteNode(root->left, key); else root->right = deleteNode(root->right, key); return root; } } }; [LeetCode 450.Delete Node in a BST][]就是对BST删除操作的考察,这个操作我真的讲的很细致了。如何检验自己是否听明白了呢?没错,直接后继就是留给你检验自己有没有听懂的机会,首先你要推导出直接后继对应的是当前结点的什么结点,其次需要分析像分析直接前驱那样,分析直接后继中的情况,答案我会放在Github上,独立思考后可以进行参考o! ## 回顾总结 ## **1.BST模版 2.树的直接前驱/后继结点 3.BST中序遍历结果对应升序数组 4.记录前驱结点的思想 5.利用指针位置的不同显性化出分类讨论出的结果 6.关注我** 之后的博客风格可能都会像这样了,可能不会专门的去做LeetCode刷题栏目了,会专门拆开某个算法知识点,可能有针对性的对应一些题目留给大家去思考。另外之前自己基于nodejs和github搞了个博客,由于github对国内是真的不友好,可能之后会基于gitee再创建个博客吧。各位同学如果觉得我的博客内容写得不错求你们给个关注8!我会努力写出更优质的内容的! github地址:[https://github.com/18260036169/LeetCode-Tree][https_github.com_18260036169_LeetCode-Tree] [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NDA2NjU2_size_16_color_FFFFFF_t_70_pic_center]: /images/20210527/0e72fd4a0c4c45c1910e09b9a11b7824.png [LeetCode 450.Delete Node in a BST]: https://leetcode-cn.com/problems/delete-node-in-a-bst/ [https_github.com_18260036169_LeetCode-Tree]: https://github.com/18260036169/LeetCode-Tree
还没有评论,来说两句吧...