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라는 실수 반복함.
https://leetcode.com/problems/delete-node-in-a-bst/discuss/746703/Python-iterative-solution
이전 노드를 따로 추적해야해서 불편함. 이전 노드가 있냐없냐에 따라 예외 상황 발생함.
val만 바꾸고 left,right 안 바꿀 수 있었음!
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에 비해 코드 간결. 작은 트리는 큰 트리에 포함됨 --> 재귀적
재귀 함수 빠지는 조건이 신기함. 밑에 자식 한 쪽없으면 가지고 있는 자식 주고 빠짐.
제거하고 어떤 것으로 대체해야하는지 확실한 로직가지고 코드 만들기
일반적인 예시 놓치지 않기