BST中删除一个节点，并返回新的BST

喜欢ヅ旅行 2022-10-28 10:07 77阅读 0赞

/** * BST中删除一个节点，并返回新的BST * @author zhaizhg * */
    public class DeleteNumInBST { 
    
    	public static void main(String[] args) { 
    		TreeNode root = new TreeNode(5);
    		root.left = new TreeNode(2);
    		root.right = new TreeNode(6);
    		root.left.left = new TreeNode(1);
    		root.right.right = new TreeNode(7);
    		root.left.right = new TreeNode(4);
    		root.left.right.left = new TreeNode(3);
    		TreeNode node = delete(root, 2);
    		System.out.println(node.left.val);
    
    	}
    	
    	static TreeNode delete(TreeNode node, int num) { 
    		if (node == null) return null;
    		if (node.val == num) { 
    			// 如果没有左右子节点
    			if (node.left == null && node.right == null) return null;
    			// 如果没有左节点
    			if (node.left == null) return node.right;
    			// 如果没有右节点
    			if (node.right == null) return node.left;
    			// 如果左右节点都有,找到左或右子树的最小节点来替换他的位置
    			// 再把这个最小节点给移除
    			TreeNode minNode = getMin(node.right);
    			node.val = minNode.val;
    			node.right = delete(node.right, minNode.val);
    		} else if (node.val > num) { 
    			node.left = delete(node.left, num);
    		} else if (node.val < num) { 
    			node.right = delete(node.right, num);
    		}
    		return node;
    			
    	}
    	
    	static TreeNode getMin(TreeNode node) { 
    		while (node.left != null) { 
    			node = node.left;
    		}
    		return node;
    	}
    
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode——树：BST

BST -------------------- 目录 1. 概述 2. 修剪二叉查找树（LeetCode669） 3. 寻找二叉查找树的第k个元素（Lee

分手后的思念是犯贱/ 2023年07月12日 14:38/ 0 赞/ 53 阅读

相关数据结构 - 二叉排序树BST(创建、遍历、删除节点)

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

红太狼/ 2023年07月03日 07:24/ 0 赞/ 24 阅读

相关 BST中删除一个节点，并返回新的BST

/ BST中删除一个节点，并返回新的BST @author zhaizhg / public class DeleteNumInBST {

喜欢ヅ旅行/ 2022年10月28日 10:07/ 0 赞/ 78 阅读

相关在BST中插入一个数

/ 在BST中插入一个数 / public class InsertNumInBST { public static void mai

Myth丶恋晨/ 2022年10月28日 10:06/ 0 赞/ 98 阅读

相关在BST中查找一个数是否存在

/ 判断二叉搜索树中的某个数是否存在 @author zhaizhg / public class FindOneInBST { p

怼烎@/ 2022年10月28日 08:02/ 0 赞/ 175 阅读

相关 BST插入（建立）、删除、查找和排序

实验要求： 1. 设计BST 的左右链存储结构，并实现BST插入（建立）、删除、查找和排序算法。 2. 实现折半查找算法。 3. 实验比较：设计并产生实验测试数据，考察

男娘i/ 2022年03月26日 01:48/ 0 赞/ 163 阅读

相关 (BST二叉搜索树 1.2)Leetcode Delete no in a BST(删除二叉搜索树中的节点)

Given a root node reference of a BST and a key, delete the node with the given key in th

小鱼儿/ 2022年02月28日 00:34/ 0 赞/ 234 阅读

相关 bst树的学习

二叉排序树（BST）它是一种对排序和查找都很有用的特殊二叉树具有下列性质 1.若它的左子树不为空，左子树上所有节点的值都小于根节点。

柔情只为你懂/ 2022年01月27日 13:35/ 0 赞/ 182 阅读

相关 [BZOJ]BST again

Description 求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模） Input 第一行一个整数T，表示数

偏执的太偏执、/ 2021年09月30日 00:32/ 0 赞/ 152 阅读

相关 BST删除操作（二叉搜索树）

BST的删除操作向来被认为难度很大，因为它不同于插入，定位到了那个该插入的位置选择左边/右边进行插入即可，而删除操作则需要分成以下三种情况进行讨论，删除难度从上到下依次递增：

雨点打透心脏的1/2处/ 2021年06月10日 20:39/ 0 赞/ 434 阅读