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:
BST(이진 탐색 트리)의 루트 노드 참조와 키가 주어졌을 때, BST에서 주어진 키를 가진 노드를 삭제하고 업데이트된 BST의 루트 노드 참조를 반환합니다.
삭제 과정은 대체로 두 단계로 나뉩니다:
1. 삭제할 노드를 찾습니다.
2. 노드를 찾았다면 해당 노드를 삭제합니다.
[0, 10^4]
범위에 있습니다.-10^5 <= Node.val <= 10^5
root
는 유효한 이진 탐색 트리입니다.-10^5 <= key <= 10^5
트리의 높이에 대한 시간 복잡도 O(height of tree)
로 이 문제를 해결할 수 있습니까?
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;
}
}