Tree专题:Delete a Node in BST 【hard】

这题是我一直想做,但是拖延症一直没做的题。【拖了估计有3个月。。。】

今天一做一直感觉就快做出来了,但是越做感觉越难。我一开始的思路是找到一个parent,这个parent的left,或者right就是要删的那个。在parent要方便我们操控链接node。但是发现比如删了parent的leftnode。这时候leftnode的子孙要顶上来。比如leftNode.rightNode这个时候补上那个位置,那原本leftnode.rightnode的子孙的links又要改。。。感觉好麻烦。。

看了一下我半年前的笔记, 原来是要用recursion。。还需要用一个findMin()的function,找到rightsubtree里最小的,然后顶上来做new Node. 【findMin其实就是跑到leftmost node】。然后再把那个node给删了。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,357评论 0 33
  • 总结类型: 完全子树(#222) BST(左右子树值的性质,注意不仅要满足parent-child relatio...
    __小赤佬__阅读 3,994评论 0 0
  • 传送门:http://www.jianshu.com/p/10121d699c32 文章不错·先收藏·
    永远都能阅读 1,508评论 0 0
  • 求职季和毕业季混在一起的烦恼时节。 归结起来还是内心的不确定在作祟。 其实种瓜得瓜,很多结果应该更淡然,努力毕竟不...
    木小雨阅读 1,360评论 0 0
  • 又是一年找工作潮,大学生好多面临找工作的困难。想创业,但是找不到好的门路,那么我就给大家,列举一些,当下成本比较小...
    荻花令阅读 5,434评论 1 0

友情链接更多精彩内容