首页 > 试题广场 >

删除一个二叉搜索树中的节点

[编程题]删除一个二叉搜索树中的节点
  • 热度指数：845 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个节点数目为N的二叉搜索树的根节点root和一个值key，请你完成删除一个节点的功能
1.如果二叉搜索树有节点里面存在有该值的key，那么删除该节点，然后调整该树，使其还是一颗二叉搜索树，返回这颗新树的根节点
2.如果不存在有节点的值等于key，则不删除，直接返回原树的根节点
3.root里面的节点值各不相同
4.该题返回的二叉搜索树不唯一，你返回合法的一颗即可
5.该题有O(H)的时间复杂度的算法，H为树的高度，一种方法如下:
5.1如果key大于当前节点值，则去当前节点的右子树中删除；
5.2如果key小于当前节点值，则去当前节点的左子树中删除；
5.3如果key就是当前节点值，分为以下三种情况：
5.3.1当前节点只无左子树：删除了该节点，其右子树顶替其位置；
5.3.2当前节点只无右子树：删除了该节点，其左子树顶替其位置；
5.3.3其左右子树都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
5.3.4其左右子树都无：直接删除该节点即可


数据范围:





示例1

输入

{4,2,7,1,3,#,8},2

输出

{4,3,7,1,#,#,8}

说明

删除节点2，变为：
当然，如下二叉搜索树也视为正确解法之一:
示例2

输入

{4,2,7,1,3,#,8},5

输出

{4,2,7,1,3,#,8}

说明

没有值为5的节点，不删除，返回原树
示例3

输入

{},2

输出

{}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
Isolated_Island头像 Isolated_Island 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public TreeNode deleteNode (TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            if (root.left == null || root.right == null) {
                return root.left == null ? root.right : root.left;
            }
            TreeNode node = root.left;
            while (node.right != null) {
                node = node.right;
            }
            node.right = root.right;
            return root.left;
        }
        root.left = this.deleteNode(root.left, key);
        root.right = this.deleteNode(root.right, key);
        return root;
    }
}

发表于 2022-05-23 17:08:04 回复(0)
C++
牛娃牛娃头像 牛娃牛娃

1） 返回值是节点 参数是root  和一个 要删除的值key

2） 情况1：没有找到要删除的节点 就是root为空 直接返回root

if(root==nullptr)return root;

3） 如果 root->val =key

a)      情况2：如果左右孩子都为空，直接删除 返回null

if(root->left==nullptr&&root->right==nullptr)return nullptr;

b)     情况3：左孩子为空，右孩子不为空，删除节点后，右孩子补位，返回右孩子为根节点

if(root->left==nullptr)return root->right;

c)      情况4：右孩子为空，左孩子不为空，删除节点后，左孩子补位，返回左孩子为根节点

if(root->right==nullptr)return root->left;

d)     情况5：root左右孩子都不为空 ，把请root的整个左挪到root右孩子里面最左孩子的位置  返回 root的右孩子为跟根节点

if(root->left!=nullptr&&root->right!=nullptr)

{TreeNode *cur =root->right;//查找右子树最左面的节点

  while(cur->left!=nullptr){cur=cur->left; }

//把要删除的节点的左子树放在cur的左子树位置cur->left=root->left;

//保存root节点TreeNode* tmp =root;

//返回旧root的右孩子作为新的root  root=root->right;delete tmp;

 return root;}

4） 如果 root->val> key root的左更新为递归函数 参数是root左 和key

if(root->val>key) root->left=deleteNode(root->left,key);

5）  如果 root->val< key root的右更新为递归函数 参数是root右 和key

if(root->val<key)root->right=deleteNode(root->right,key);

6）  最后返回根 return root 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param key int整型 
     * @return TreeNode类
     */
    TreeNode* deleteNode(TreeNode* root, int key) {
        // write code here
        if(root==nullptr)return root;
        if(root->val==key){
            if(root->left==nullptr&&root->right==nullptr)return nullptr;
            if(root->left==nullptr)return root->right;
            if(root->right==nullptr)return root->left;
            if(root->left!=nullptr&&root->right!=nullptr){
                TreeNode *cur =root->right;//查找右子树最左面的节点
                while(cur->left!=nullptr){
                    cur=cur->left;
                }
                //把要删除的节点的左子树放在cur的左子树位置
                cur->left=root->left;
                //保存root节点
                TreeNode* tmp =root;
                //返回旧root的右孩子作为新的root
                root=root->right;
                delete tmp;
                return root;
            }
            
        }
        if(root->val>key) root->left=deleteNode(root->left,key);
        if(root->val<key)root->right=deleteNode(root->right,key);
        return root;
    }
};

发表于 2022-03-15 11:30:25 回复(0)
Rust
老刘001头像 老刘001 
/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root TreeNode类 
        * @param key int整型 
        * @return TreeNode类
    */
    pub fn deleteNode(&self, mut root: Option<Box<TreeNode>>, key: i32) -> Option<Box<TreeNode>> {
        // write code here
        use std::cmp::Ordering::{Greater, Less, Equal};

        if root.is_some() {
            match key.cmp(&root.as_ref()?.val) {
                Greater => {
                    root.as_mut()?.right = self.deleteNode(root.as_mut()?.right.take(), key);
                },
                Less => {
                    root.as_mut()?.left = self.deleteNode(root.as_mut()?.left.take(), key);
                },
                Equal => {
                    match (root.as_ref()?.left.is_some(), root.as_ref()?.right.is_some()) {
                        (false, false) => {return None},
                        (false, true) => {return root.as_mut()?.right.take()},
                        (true, false) => {return root.as_mut()?.left.take()},
                        (true, true) => {
                            let successor = self.min(&root.as_mut()?.right);
                            root.as_mut()?.right = self.deleteNode(root.as_mut()?.right.take(), successor);
                            root.as_mut()?.val = successor;
                        }
                    }
                }
            }

            root
        } else {
            None
        }
    }

    fn min(&self, node: &Option<Box<TreeNode>>) -> i32 {
        assert!(node.is_some());
        if node.as_ref().unwrap().left.is_some() {
            self.min(&node.as_ref().unwrap().left)
        } else {
            node.as_ref().unwrap().val
        }
    }
}

发表于 2023-09-01 09:19:40 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
import _"fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param key int整型 
 * @return TreeNode类
*/
func deleteNode( root *TreeNode ,  key int ) *TreeNode {
    if root==nil{
        return nil
    }else if root.Val>key{
        root.Left=deleteNode(root.Left,key)
        return root
    }else if root.Val<key{
        root.Right=deleteNode(root.Right,key)
        return root
    }else{
        if root.Right==nil{
            return root.Left
        }else if root.Left==nil{
            return root.Right 
        }else{
            min:=order(root.Right).Val
            root.Val=min
            root.Right=deleteNode(root.Right,min)
            return root
        }
    }
}

func order(root *TreeNode)*TreeNode{
    for root.Left!=nil{
        root=root.Left
    }
    return root
}

发表于 2023-03-16 14:25:45 回复(0)
Java
冲啊啊123头像 冲啊啊123 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param key int整型 
     * @return TreeNode类
     */
    public TreeNode deleteNode (TreeNode root, int key) {
        // write code here
        if(root==null){
            return root;
        }
        //处理左右子树
        TreeNode left=deleteNode(root.left, key);
        TreeNode right = deleteNode(root.right,key);
        
        if(root.val==key){
            if(right!=null){
                if(left!=null){
                    //将处理后的左子树转移到其右子树的最左节点的左子树上
                    TreeNode rightLeft = right;
                    while(rightLeft.left!=null){
                        rightLeft=rightLeft.left;
                    }
                    rightLeft.left=left;
                }
                return right;
            }else if(left!=null){
                return left;
            }else{
                return null;
            }
        }else{
            
            //重新缝补左右节点
            root.left=left;
            root.right=right;
            return root;
        }

    }
}

发表于 2022-11-21 22:53:06 回复(0)
布加迪.威龙头像 布加迪.威龙 
static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return nullptr;
}
();
class Solution {
  public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root)
            return root;
        if (root->val == key) {
            if (!root->left && !root->right) {
                delete root;
                return NULL;
            } else if (!root->left) {
                TreeNode* node = root->right;
                delete root;
                return node;
            } else if (!root->right) {
                TreeNode* node = root->left;
                delete root;
                return node;
            } else {
                TreeNode* cur = root->right;
                while (cur->left)
                    cur = cur->left;
                cur->left = root->left;
                TreeNode* temp = root;
                root = root->right;
                delete temp;
                return root;
            }
        }
        if (root->val > key)
            root->left = deleteNode(root->left, key);
        if (root->val < key)
            root->right = deleteNode(root->right, key);
        return root;
    }
};

发表于 2022-07-21 17:05:13 回复(0)
提交观点

问题信息

树
上传者：牛客301499号
难度：
6条回答 1538浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号