[Binary Search Tree, Medium] Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/description/?envType=study-plan-v2&envId=leetcode-75

처음에 while 사용해서 풀어보려 했는데 장황해졌다.
재귀적으로 접근하는게 코드 가독성이 좋다고 판단함

핵심은 지울 노드가 자식을 어떻게 가지고 있느냐에 따라 달라짐
만약 left, right 둘 다 있다면 이진 탐색 트리 특성 상 현재 root의 오른쪽 서브트리로부터 가장 작은 값을 root자리로 대치해야 함

• 삭제할 노드를 찾을 때까지 재귀 호출
• 찾은 경우
  • 자식이 없거나 하나: 그대로 부모에 연결 (root.left = child or root.right = child)
  • 자식이 둘: 오른쪽 서브트리에서 가장 작은 노드를 찾아 대체 후 재귀적으로 삭제 (중복제거)

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

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

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

        return root;
    }

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