LeetCode 풀기 - 450. Delete Node in a BST

450. Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/

Delete Node in a BST - LeetCode

문제)

솔루션1) - recursive

이진 탐색 트리에서 노드 삭제 구현 여부를 물어보는 문제입니다.

재귀적인 방법으로 노드 삭제를 구현하는 일반적인 방법입니다.

 

Example 1) 형태로 결과가 나오도록 구현하였습니다.

삭제 대상 노드이 오른쪽 subtree에서 min에 해당하는 node로 치환해서 삭제를 구현합니다.

 

# 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 root is None:
            return None
        
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else:                
                # 오른쪽 서브트리에서 min 노드 탐색
                min_node = self.findMinNode(root.right)
                
                # root에 값 복사
                root.val = min_node.val
                root.right = self.deleteNode(root.right, min_node.val)
            
        return root
    
    def findMinNode(self, node):
        while node.left:
            node = node.left
        return node

솔루션2) - recursive

Example 2) 형태로 결과가 나오도록 구현하였습니다.

삭제 대상 노드의 왼쪽 subtree에서 max에 해당하는 node로 치환해서 삭제를 구현합니다.

# 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 root is None:
            return None
        
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if root.left is None:
                return root.right
            else:
                # 왼쪽 서브트리에서 max 노드 탐색
                max_node = self.findMaxNode(root.left)
                
                # root에 값 복사
                root.val = max_node.val
                root.left = self.deleteNode(root.left, max_node.val)
            
        return root
    
    def findMaxNode(self, node):
        while node.right:
            node = node.right
        return node