(模板)删除二叉树上的某个节点

小灰灰 2023-01-10 05:29 73阅读 0赞

\#\#\# 解题思路

要删除的节点分为三种情况

1.节点既没有左子树也没有右子树:直接删除即可

2.节点只有左子树或者右子树:用子节点替换即可

3.既有左子树又有右子树:找到该节点的后继(比该节点大的最小数),替换后递归删除后继

\#\#\# 代码

class Solution {
    public:
        void delNode(TreeNode* &root,int val){   //加引用可以直接操作节点
            if(!root) return;
            if(root->val == val){  
                if(!root->left && !root->right) root = nullptr;  //没有左子节点和右子节点,直接删除
                else if(!root->left) root = root->right;  //用子树覆盖
                else if(!root->right) root = root->left;  //用子树覆盖
                else{  //找前驱
                    TreeNode* p = root->right;
                    while(p->left) p = p->left; //找前驱
                    root->val = p->val;
                    delNode(root->right,p->val);
                }
            }
            else if(root->val < val) delNode(root->right,val);
            else delNode(root->left,val);
        }
        TreeNode* deleteNode(TreeNode* root, int key) {
            delNode(root,key);
            return root;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，73人围观）

还没有评论，来说两句吧...

相关阅读

相关 java二叉树-删除节点

要求 1. 如果删除的节点是叶子节点，则删除该节点 2. 如果删除的节点是非叶子节点，则删除该子树. 3. 测试，删除掉 5 号叶子节点和 3 号子树. 4. 完成

ゝ一世哀愁。/ 2024年03月27日 13:56/ 0 赞/ 53 阅读

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

450.删除二叉搜索树中的节点题干描述解题思路递归 1. 确定递归函数参数以及返回值 2. 确定终

我不是女神ヾ/ 2023年10月16日 11:43/ 0 赞/ 21 阅读

相关数据结构 - 二叉树(删除节点)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZ

约定不等于承诺〃/ 2023年07月03日 04:51/ 0 赞/ 89 阅读

相关二叉排序树的创建和节点删除

二叉排序树-BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大

曾经终败给现在/ 2023年05月31日 15:29/ 0 赞/ 37 阅读

相关 (模板)删除二叉树上的某个节点

\\\ 解题思路要删除的节点分为三种情况 1.节点既没有左子树也没有右子树:直接删除即可 2.节点只有左子树或者右子树:用子节点替换即可 3.既有左子树又有右子树:找

小灰灰/ 2023年01月10日 05:29/ 0 赞/ 74 阅读

相关【lintcode】删除二叉查找树的节点

描述给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。

Bertha 。/ 2022年05月20日 07:58/ 0 赞/ 204 阅读

相关 (方法)利用层序遍历返回二叉树上的节点

我们在查找二叉树上的节点时,会通过递归去进行遍历,如果我们要把这个节点作为函数返回值进行返回的话,递归遍历法就无法满足我们可以通过层序遍历去查找结点然后进行返回,只需一个辅

以你之姓@/ 2022年05月09日 09:20/ 0 赞/ 75 阅读

相关删除子父节点中的某个节点

import java.sql.Connection; import java.sql.ResultSet; import java.sql.SQLException;

叁歲伎倆/ 2022年03月29日 06:28/ 0 赞/ 293 阅读

相关二叉查找树-插入、查找某个值节点、查找前驱或后继、删除

/ 二叉查找树插入查找前驱、后继删除 https://www.cnblogs.com/skywang12345/p/3576373.html

╰半橙微兮°/ 2021年11月19日 15:44/ 0 赞/ 286 阅读

相关二叉排序树删除节点

二叉排序树，是非常特殊的一种树，具体定义见任何一本数据结构书籍。其删除一个节点需要考虑对应节点的状态，具体的说就是，是否存在左右节点，等等。需要按照以下情况讨论。 1.查

- 日理万妓/ 2021年11月08日 22:18/ 0 赞/ 307 阅读