【LeetCode】 删除二叉搜索树中的节点 Java 题解
题目描述
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;如果找到了,删除它。
复制代码
思路分析
今天的算法题目是二叉搜索树题目。二叉搜索树具有如下性质:1. 左子树的所有节点都小于当前根节点的值。2. 右子树的所有节点都大于当前根节点的值。3.左右子树都是二叉搜索树。
题目要求我们删除某个节点,并返回根节点。对于二叉树的题目,我们常用的解决办法是递归求解。
具体到这个题目,我们需要找到目标值。在查找值的时候,充分应用二叉搜索树的性质,提升查找效率。
若没有目标值,或者 root 为空,直接返回即可。
当找到目标值节点,则需再次分情况讨论。情况 1,当前节点为叶子节点,直接删除。情况 2,当前节点只有左子节点或者右子节点,则删除当前节点,左子节点或者右子节点到当前位置即可。情况 3,左右子节点都有,其左子树转移到其右子树的最左节点的左子树上,然后右子树顶替其位置,由此删除了该节点。实现代码如下,供参考。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n),空间复杂度是 O(n)
这个题目比较复杂,需要熟悉二叉搜索树的性质,并且多次分情况讨论,才能更好的理解,需要多加练习。
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/cc56d7195e854ba27a8ebaa30】。文章转载请联系作者。
评论