这题是我一直想做,但是拖延症一直没做的题。【拖了估计有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给删了。