2分探索木からノードを削除する Delete Node in a BST in LeetCode
問題
2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。
解法
以下のステップで解く
- 2分探索でkeyを見つける
- 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。
- 右側のサブツリーから最小値のノードを削除する
- (削除するノードのleft, rightのどちらかがnullの場合はnullではない方のサブツリーを削除するノードと置き換える)