BST: 450. Delete Node in a BST

450. Delete Node in a BST

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root

        if root.val < key: # key 가 더 크면, 오른쪽으로 내려가서 삭제
            root.right = self.deleteNode(root.right, key)

        elif root.val > key: # key 가 더 작으면, 왼쪽으로 내려가서 삭제
            root.left = self.deleteNode(root.left, key)
        else: # root.val == key: # 아니면, root 삭제
            if not root.left: # root 의 왼쪽 노드가 없으면,
                return root.right # 오른쪽 반환
            elif not root.right: # root 의 오른쪽 노드가 없으면,
                return root.left
            else: # 둘다 있으면 
                # root 삭제 전에, 오른쪽 노드의 가장 작은 값을 root 에 적용하고, 
                # 오른쪽 노드의 가장 작은 노드(왼쪽으로 내려가야함)를 삭제해야 하므로
                cur = root.right
                while cur.left:
                    cur = cur.left

            root.val = cur.val
            root.right = self.deleteNode(root.right, cur.val)
        
        return root # 현재 노드

 

https://youtu.be/LFzAoJJt92M?si=_LrfMfVYxmtP2HPL

 

 

def delete(node, val):

    if not node:

        return None # 빼먹으면 안됨

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        
        def minValue(node):
            # 현재 노드 트리에서 최소값을 가진 노드 리턴.
            # 그래서, 왼쪽으로만 내려가면되고, 왼쪽 끝 리프노드를 리턴

            cur = node

            while cur.left:
                cur = cur.left # 이게 내려가는 건데.

            # 원래 while cur: 이렇게 하면,
            # while 문 끝나면, cur 이 null 이 되므로
            # while cur.left 하면
            # cur.left 가 null 이 되었을때 while 문이 나오므로.
            # cur 는 왼쪽 끝 leaf 노드가 됨
            return cur

        def delete(node, val):
            if not node: 
                return None # 빼먹으면 안됨

            if val < node.val: # 삭제 할 값이, 현재 노드 값보다 작으면, 왼쪽으로 내려가서 삭제
                node.left = delete(node.left, val)
            elif val > node.val: # 삭제 할 값이, 현재 노드 값보다 크면, 오른쪽으로 내려가서 삭제
                node.right = delete(node.right, val)
            else: # 삭제할 값이 현재 값이면
                if not node.left: # 왼쪽 자식이 없으면
                    return node.right # 오른쪽 자식 리턴
                elif not node.right: # 오른쪽 자식이 없으면
                    return node.left
                elif node.left and node.right: # 둘다 있으면
                    # 현재꺼 삭제하면
                    # 오른쪽에서 가장 작은 노드가 현재 노드로 올라와야 하니
                    # 오른쪽에서 가장 작은 노드를 우선 찾음
                    rightMin = minValue(node.right)
                    
                    # 현재 노드값을 rightMin 값으로 바꾸고
                    node.val = rightMin.val
                    #현재 노드의 오른쪽에서 이 rightMin 값을 삭제
                    node.right = delete(node.right, rightMin.val)
            return node

        return delete(root, key)