[leetcode #450] Delete Node in a BST

Problem

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Constraints:

・ The number of nodes in the tree is in the range [0, 10⁴].
・ -10⁵ <= Node.val <= 10⁵
・ Each node has a unique value.
・ root is a valid binary search tree.
・ -10⁵ <= key <= 10⁵

Follow up: Could you solve it with time complexity O(height of tree)?

Idea

長いこと解いてみたが、ずっと間違っていて、あきらめた.最近头が回転して来ない感じがしてとても悲しいです...🥲
基本アルゴリズムは考えやすい.
指定したキー値が現在のノードより大きい場合は右側のサブツリーを参照し、小さい場合は左側のサブツリーを参照します.このとき,条件に応じてサブノードを再帰関数が返すノードに設定する.
上記の条件でナビゲーションを続行し、一致する値のノードが見つからない場合は、再帰関数でnullを返してナビゲーションを終了します.
キー値と同じノードが表示されると、左側のサブノードがnullの場合は右側のサブノード、右側のサブノードがnullの場合は左側のサブノードが返されます.すべてのサブノードがある場合は、右側のサブツリーで最小値を検索します.BSTにより,ツリーの一番左側に位置するノードが最小値となる.
keyと同じ値を持つノードを上記の手順で見つけた最小値に設定し、右側のサブノードと最小値をパラメータとしてdeleteNode再帰関数を呼び出します.treeの代わりに再帰関数を初めて呼び出してサブツリーを解析した.
簡単そうに見えますが、ノードに値を変えるのはどうしても思い出せません.ノード値を変更せずにif-else文にノード全体を置き換えようとしたため,混乱したコードが生成された.
今日の道のタイトルはメディムでも解けないので、本当にうんざりして、眠れないようです.😅

Solution

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {

        if (root == null) return null; 

        if (root.val < key)
            root.right = deleteNode(root.right, key);
        else if (root.val > key)
            root.left = deleteNode(root.left,key);

        else{
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;

            TreeNode minNode = minNext(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, root.val);
        }

        return root;
    }

    private TreeNode minNext(TreeNode node) {
        while (node.left != null) node = node.left;
        return node;
    }
}

Reference

https://leetcode.com/problems/delete-node-in-a-bst/