450. 删除二叉搜索树中的节点 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
【LeetCode|450. 删除二叉搜索树中的节点】一般来说,删除节点可分为两个步骤:
- 首先找到需要删除的节点;
- 如果找到了,删除它。
文章图片
输入: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
输出: []
思考 我们删除一个节点,首先考虑特殊情况
- 该树为空,直接返回null
- 该节点为树的根节点,并且没有左右子树,返回null
- 处理
- 遍历左子树
- 遍历右子树
- pre代表访问该节点的父节点,初始化为null
- root代表正在访问的节点
- key
- 如果删除的节点不是根节点,preOrder函数返回null,deleteNode返回root
- 如果删除的节点是根节点,preOrder函数返回新的根tempRoot,deleteNode返回tempRoot
- 如果该节点的值等于key,说明需要删除此节点
文章图片
此图代表left和right非空时
- root代表需要删除的节点
- left代表root的左孩子(可能为null)
- right代表root的右孩子(可能为null)
- pre代表root的父节点,但是我们不知道root是pre的左孩子还是右孩子
- 但是由于该树是搜索二叉树,所以我们可以根据pre.val和root.val来判断
- 我们只需把b(可能为null)移动到c(可能为null)的左子树即可
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return null;
if(root.val==key){
if(root.left==null&&root.right==null)
return null;
}
TreeNode temp =null;
temp = preOrder(null,root,key);
if(temp!=null) return temp;
return root;
}private TreeNode preOrder(TreeNode pre, TreeNode root, int key) {
TreeNode temp = null;
if(root.val == key){TreeNode temproot = null;
TreeNode left=root.left;
TreeNode right=root.right;
if(right==null){
temproot = left;
}else if(right!=null){
if(left==null){
temproot=right;
}else{
TreeNode righttemp = right;
while (righttemp.left!=null){
righttemp = righttemp.left;
}
righttemp.left=left.right;
left.right=right;
temproot =left;
}
}
if(pre==null){
return temproot;
}
if(pre!=null){
if(pre.val>root.val){
pre.left= temproot;
}
if(pre.val
推荐阅读
- leetcode|递归回溯的几个小题目
- 数据结构与算法|数据结构(第二章(一))
- 算法刷题小模版|八大排序的思想及其代码
- 算法|递归和非递归详解
- OJ|OJ---腐烂的橘子
- java|杂项-Java(JCP)
- 编程语言|2020 年编程语言盘点展望(Java 老兵不死,Kotlin 蓄势待发)
- ★My|业界呼吁Java源代码尽早开放 Sun犹豫不决
- Java|Java I/O