[Leetcode] 450. Delete Node

jong_p·2021년 11월 22일
1

영혼의 알고리즘

목록 보기
1/19

21.11.22
solved 60min

BST에서 key 값을 삭제하는 문제.

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root
        
        if root.val==key:
            if not root.right:
                return root.left
            par=None
            trav=root.right
            while trav.left:
                par=trav
                trav=trav.left
            
            if not par:
                trav.left=root.left
                return trav
            par.left=None
            trav.left=root.left
            trav.right=root.right
            return trav
        
        par=None
        trav=root
        leftFlag=True
        while trav and trav.val!=key:
            par=trav
            if key<trav.val:
                leftFlag=True
                trav=trav.left
            else:
                leftFlag=False
                trav=trav.right
        
        
        #no such key:
        if not trav:
            return root
        
        rPar=None
        rTrav=trav.right
        
        #no first right child
        if not rTrav:
            if leftFlag: par.left=trav.left
            else: par.right=trav.left
            return root
        
        while rTrav.left:
            rPar=rTrav
            rTrav=rTrav.left
            
        if leftFlag: par.left=rTrav
        else: par.right=rTrav
        
        rTrav.left=trav.left
        if rPar:
            rPar.left=rTrav.right
            rTrav.right=trav.right
            
                
                
        
        return root

<접근>

무언가를 삭제하게되면 그것을 대체할 것을 찾아야함.
key의 right child에서 가장 작은 것(most left side child)로 대체를 하면 BST 조건 만족함.

예외조건이 많아서 까다로웠음.

key가 루트일 경우.
trav(node with key)가 rightChild를 가지지 않을 경우.
rightChild가 바로 left child를 가지지 않을 경우.

<과정>

예외조건을 state variable로 처리하려다보니 조건이 너무 많아져서 복잡했음. 그래서 갈아엎고, root.val==key인 경우만 따로 처리했음. 예외 조건 두개만 다루니까 그래도 할만 했음.

 if rPar:
            rPar.left=rTrav.right
            rTrav.right=trav.right

여기서 rPar.left=None이라고 했다가 마지막 에러를 냄. rTrav가 rigth chld를 가질 수 있음.
→ 좀 더 일반적인 상황에 대해 생각해야함.

        while rTrav.left:
            rPar=rTrav
            rTrav=rTrav.left코드를 입력하세요

while not rTrav.left라는 실수 반복함.

<솔루션>

iteration

https://leetcode.com/problems/delete-node-in-a-bst/discuss/746703/Python-iterative-solution
이전 노드를 따로 추적해야해서 불편함. 이전 노드가 있냐없냐에 따라 예외 상황 발생함.
val만 바꾸고 left,right 안 바꿀 수 있었음!

recursion
def deleteNode(root, key):
	if not root: return None
	if root.val > key: 
		root.left = deleteNode(root.left, key)
	elif root.val < key: 
		root.right = deleteNode(root.right, key)
	else:
		if not (root.left and root.right): 
			return root.left or root.right
		root.val = findClosest(root.right).val
		root.right = deleteNode(root.right, root.val)
	return root

def findClosest(node):
	while node.left:
		node = node.left
	return node

https://leetcode.com/problems/delete-node-in-a-bst/discuss/254235/Python-Recursion-Hibbard-Deletion
iteration에 비해 코드 간결. 작은 트리는 큰 트리에 포함됨 --> 재귀적
재귀 함수 빠지는 조건이 신기함. 밑에 자식 한 쪽없으면 가지고 있는 자식 주고 빠짐.

<개선점>

제거하고 어떤 것으로 대체해야하는지 확실한 로직가지고 코드 만들기
일반적인 예시 놓치지 않기

profile
알고리즘 정리 좀 해볼라고

0개의 댓글