2分探索木からノードを削除する Delete Node in a BST in LeetCode

問題

2分探索木とint型のkeyが与えられる。BSTからkeyの要素を削除する問題。

leetcode.com

解法

以下のステップで解く

  1. 2分探索でkeyを見つける
  2. 削除するノードの右側のサブツリーの最小値を持つノードを削除するノードに置き換える。
  3. 右側のサブツリーから最小値のノードを削除する
  4. (削除するノードのleft, rightのどちらかがnullの場合はnullではない方のサブツリーを削除するノードと置き換える)

f:id:atiek1121:20170613091118p:plain

ソースコード