LeetCode 75: 450. Delete Node in a BST

김준수·2024년 3월 29일
0

LeetCode 75

목록 보기
42/63
post-custom-banner

Description

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.

BST 노드 삭제

문제 설명

BST(이진 탐색 트리)의 루트 노드 참조와 키가 주어졌을 때, BST에서 주어진 키를 가진 노드를 삭제하고 업데이트된 BST의 루트 노드 참조를 반환합니다.

삭제 과정은 대체로 두 단계로 나뉩니다:
1. 삭제할 노드를 찾습니다.
2. 노드를 찾았다면 해당 노드를 삭제합니다.

예제 1:

  • 입력: root = [5,3,6,2,4,null,7], key = 3
  • 출력: [5,4,6,2,null,null,7]
  • 설명: 삭제할 키가 3입니다. 값이 3인 노드를 찾아 삭제하면, [5,4,6,2,null,null,7]의 형태로 트리가 재구성됩니다.
    Example 1

예제 2:

  • 입력: root = [5,3,6,2,4,null,7], key = 0
  • 출력: [5,3,6,2,4,null,7]
  • 설명: 트리에 값이 0인 노드가 없습니다.

예제 3:

  • 입력: root = [], key = 0
  • 출력: []
  • 설명: 트리가 비어있습니다.

제약 조건

  • 트리의 노드 수는 [0, 10^4] 범위에 있습니다.
  • -10^5 <= Node.val <= 10^5
  • 각 노드는 유일한 값을 가집니다.
  • root는 유효한 이진 탐색 트리입니다.
  • -10^5 <= key <= 10^5

후속 질문

트리의 높이에 대한 시간 복잡도 O(height of tree)로 이 문제를 해결할 수 있습니까?

Solution

public 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;
            }
            // 두 개의 자식을 가진 경우
            TreeNode minNode = root.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }

            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        }
        return root;
    }
}
post-custom-banner

0개의 댓글