450. Delete Node in a BST

Delete Node in a BST - LeetCode

 

주어진 이진 탐색 트리 (BST)의 루트 노드 참조와 키 (값)가 주어집니다.
이 BST에서 주어진 키와 동일한 값을 가지는 노드를 삭제하고, 삭제한 후의 BST의 루트 노드 참조를 반환합니다.
삭제 과정을 다음과 같이 나눌 수 있습니다:
1. 삭제할 노드를 찾습니다.
2. 노드를 찾으면 삭제합니다.

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:

1. Search for a node to remove.
2. 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: []

문제 요약:

주어진 BST에서 특정 키를 가진 노드를 삭제한 후의 BST를 반환하는 문제입니다.

 

풀이과정 설명:

이 문제는 재귀적으로 BST를 탐색하고 노드를 삭제하는 작업을 수행하는 것이 주요합니다. 주요 풀이 단계는 다음과 같습니다

1. BST에서 삭제할 노드를 찾습니다. 루트부터 시작하고, 주어진 키와 노드의 값을 비교하여 왼쪽 서브트리 또는 오른쪽 서브트리로 이동하면서 노드를 찾습니다.
2. 삭제할 노드를 찾으면 해당 노드를 삭제합니다.
   - 노드가 단말 노드 (자식이 없는 노드)인 경우, 해당 노드를 바로 삭제하거나 null로 대체합니다.
   -  노드가 하나의 자식만 가지는 경우, 해당 노드를 삭제하고 자식 노드로 대체합니다.
   -  노드가 두 개의 자식을 가지는 경우, 오른쪽 서브트리에서 가장 작은 값을 가진 노드를 찾고, 해당 값을 현재 노드로 복사한 다음 오른쪽 서브트리에서 해당 노드를 삭제합니다.
3. BST의 모든 작업이 완료되면 변경된 BST의 루트 노드를 반환합니다.

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;
            }else if(root.right == null){
                return root.left;
            }
            root.val = findMinValue(root.right);
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
    private int findMinValue(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node.val;
    }
}