写点什么

【LeetCode】 删除二叉搜索树中的节点 Java 题解

作者:HQ数字卡
  • 2022 年 6 月 02 日
  • 本文字数:1530 字

    阅读完需:约 5 分钟

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。


一般来说,删除节点可分为两个步骤:


首先找到需要删除的节点;如果找到了,删除它。



示例 1:
输入: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输出: []
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/delete-node-in-a-bst著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法题目是二叉搜索树题目。二叉搜索树具有如下性质:1. 左子树的所有节点都小于当前根节点的值。2. 右子树的所有节点都大于当前根节点的值。3.左右子树都是二叉搜索树。

  • 题目要求我们删除某个节点,并返回根节点。对于二叉树的题目,我们常用的解决办法是递归求解。

  • 具体到这个题目,我们需要找到目标值。在查找值的时候,充分应用二叉搜索树的性质,提升查找效率。

  • 若没有目标值,或者 root 为空,直接返回即可。

  • 当找到目标值节点,则需再次分情况讨论。情况 1,当前节点为叶子节点,直接删除。情况 2,当前节点只有左子节点或者右子节点,则删除当前节点,左子节点或者右子节点到当前位置即可。情况 3,左右子节点都有,其左子树转移到其右子树的最左节点的左子树上,然后右子树顶替其位置,由此删除了该节点。实现代码如下,供参考。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public TreeNode deleteNode(TreeNode root, int key) {        if (root == null) {            return null;        }        if (root.val > key) {            root.left = deleteNode(root.left, key);            return root;        }        if (root.val < key) {            root.right = deleteNode(root.right, key);            return root;        }
if (root.val == key) { if (root.left == null && root.right == null) { return null; } if (root.right == null) { return root.left; } if (root.left == null) { return root.right; } TreeNode successor = root.right; while (successor.left != null) { successor = successor.left; } root.right = deleteNode(root.right, successor.val); successor.right = root.right; successor.left = root.left; return successor; } return root; }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n),空间复杂度是 O(n)

  • 这个题目比较复杂,需要熟悉二叉搜索树的性质,并且多次分情况讨论,才能更好的理解,需要多加练习。

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 4
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】 删除二叉搜索树中的节点Java题解_LeetCode_HQ数字卡_InfoQ写作社区