[LeetCode] 450. Delete Node in a BST

😎풀이

1. key 값에 따라 현재 노드 값과 비교하며 깊이 우선 탐색
2. 제거해야할 노드가 탐색된 경우 다음 로직 수행
   2-1. 자식 요소가 없을 경우 null 반환
   2-2. 한 쪽 자식 요소만 존재할 경우 해당 요소로 변환
   2-3. 두 자식 요소가 모두 존재할 경우, 우측 요소 중 최소 노드를 현재 노드와 교환

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    if(!root) return null
    if(root.val > key) {
        root.left = deleteNode(root.left, key)
    } else if(root.val < key) {
        root.right = deleteNode(root.right, key)
    } else {
        if(!root.left) return root.right
        if(!root.right) return root.left
        const rightMin = getMin(root.right)
        root.val = rightMin.val
        root.right = deleteNode(root.right, rightMin.val)
    }
    return root
};

function getMin(node: TreeNode | null) {
    while(node.left) {
        node = node.left
    }
    return node
}