450. Delete Node in a BST
https://leetcode.com/problems/delete-node-in-a-bst/
BST는 Binary Search Tree의 약자로, 트리를 이루는 어떤 노드에서라도 다음과 같은 특징을 지닌다.
- 노드의 왼쪽에 있는 서브 트리의 모든 값은 해당 노드의 값보다 작다.
- 노드의 오른쪽에 있는 서브 트리의 모든 값은 해당 노드의 값보다 크다.
위의 조건을 지키면서 BST에서 노드를 삭제하는 경우는 세 가지가 있다.
- 자식이 없는 노드(리프 노드)일 때
위의 그림에서 15를 지운다고 생각해보자. 이 때는 단순하게 해당 노드를 부모 노드에서 떼어내면 성공적으로 삭제가 이루어진다.
- 자식을 하나만 가질 때
이번에는 13을 지워보자. 리프 노드와 마찬가지로 13을 지우면 될까?
여기서 13을 부모 노드에서 떼어내면 11까지 BST에서 사라져버린다!
이렇게 자식을 하나만 가지는 경우에는, 부모 노드에서 떼어내는게 아니라 자식 노드를 해당 노드의 위치로 옮겨주면 된다.
- 자식을 두 개 가질 때
자식을 두 개 가질 때는, 두 가지 방법 중 하나를 선택하면 된다.
1. 오른쪽 자식의 서브 트리에서 가장 작은 값으로 교체
2. 왼쪽 자식의 서브 트리에서 가장 큰 값으로 교체
말로만 들으면 어려우니 1번 방법을 사용해서 직접 지워보자.
10을 지운다고 가정해보자. 7이나 13을 옮길 경우, BST의 구조가 완전히 달라지게 된다.
여기서 9와 11은 어디로 가야할까? 어디로 가든 구조가 달라진다. 5나 15를 선택하더라도 결과는 마찬가지이다.
하지만, 앞서 소개한 방법을 이용한다면 구조를 해치지 않고 노드를 삭제할 수 있다.
10도 잘 삭제되었고, 기존 BST의 구조도 해치지 않았다! 만약 13이 자식을 가지고 있다고 하더라도 오른쪽 자식만 갖고 있을 것이기 때문에(왼쪽 자식이 있으려면 13보다 작아야 하는데, 그렇게 된다면 13이 선택되지 않음), 자식을 하나만 가지고 있을 때와 마찬가지로 13의 원래 위치로 옮겨주면 된다.
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) {
return null;
}
if(root.val == key) {
if(root.left == null && root.right == null){
root = null;
} else if(root.left == null) {
root = root.right;
} else if(root.right == null) {
root = root.left;
} else {
TreeNode min = root.right;
while(min.left != null) {
min = min.left;
}
root.val = min.val;
root.right = deleteNode(root.right, min.val);
}
} else if(root.val > key) {
root.left = deleteNode(root.left, key);
} else {
root.right = deleteNode(root.right, key);
}
return root;
}
}https://leetcode.com/submissions/detail/590999825/
https://github.com/sorious77/LeetCode/blob/main/code/450.java
🔔