2020년/코테
[코테 연습] Delete Node in a BST Python
위지원
2020. 9. 1. 17:39
Explore - LeetCode
LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore.
leetcode.com
class Solution:
def deleteNode(self, root, target):
idx = root.index(target)
root[idx] = root[idx+2]
root[idx + 2] = 'null'
return rootㅋㅋ... 안되는구나
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: TreeNode, key: int) -> TreeNode:
idx = root.index(key)
root[idx] = root[idx*2+1]
root[idx*2+1] = 'null'
print(root)
lis = []
tree = TreeNode(val=root[0], left=TreeNode(root[1]), right=TreeNode(root[2]))
lis.append(tree.left)
lis.append(tree.right)
l = len(root) // 2
while lis:
currentNode = lis.pop(0)
idx = root.index(currentNode.val)
if idx == l:
break
left = root[idx * 2 + 1]
right = root[idx * 2 + 2]
currentNode.left = TreeNode(left)
currentNode.right = TreeNode(right)
lis.append(currentNode.left)
lis.append(currentNode.right)
return tree
class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
lis = [root]
cnt = 0
findNode = TreeNode('null')
findIdx = -1
while True:
print(lis)
currentNode = lis.pop(0)
if currentNode is not None:
if findIdx > -1:
if cnt == findIdx*2+1:
findNode.val = currentNode.val
currentNode.val = 'null'
break
elif cnt == findIdx*2+2:
findNode.val = currentNode.val
currentNode.val = 'null'
break
if currentNode.val == key:
findNode = currentNode
findIdx = cnt
lis.append(currentNode.left)
lis.append(currentNode.right)
cnt += 1
return root[0]
0
[1,null,2]
와 같은 예외를 발견했다.
또 다른 예외 부모가 null이 되는 순간 고아가 되는 자식 노드를 해결해야한다.
class Solution:
def checkLeafNode(self, parentNode:TreeNode, node: TreeNode) -> TreeNode:
parentNode.val = node.val
node.val = 'null'
if node.right:
self.checkLeafNode(node,node.right)
elif node.left:
self.checkLeafNode(node, node.left)
else:
return
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
lis = [root]
cnt = 0
findNode = TreeNode()
findIdx = -1
while True:
if not lis:
return root
currentNode = lis.pop(0)
if currentNode is not None:
if findIdx > -1:
if cnt == findIdx*2+1 or cnt == findIdx*2+2:
self.checkLeafNode(findNode, currentNode)
#이 노드가 단말 노드인지 체크해야함 자식이 있다면 자식을 부모자리로 올려줌
break
if currentNode.val == key:
findNode = currentNode
findIdx = cnt
if currentNode.left == currentNode.right == None: #[0], 0
if cnt == 0:
return
else:#[1, null, 2], 2
currentNode.val = 'null'
return root
lis.append(currentNode.left)
lis.append(currentNode.right)
cnt += 1
return root
class Solution:
def checkNode(self, currentNode: TreeNode) :
if currentNode.right:
currentNode = currentNode.right
self.checkNode(currentNode)
elif currentNode.left:
currentNode = currentNode.left
self.checkNode(currentNode)
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
currentNode = root
while True:
if currentNode is not None:
if not root.left and not root.right:#root하나만 있는 graph인경우
if root.val == key:
return None
else:
return root
if currentNode.val == key: #발견
self.checkNode(currentNode)
break
if currentNode.val > key: #탐색
currentNode = currentNode.left
else:
currentNode = currentNode.right
else:
break
return root
아래와 같은 예외가 있다.. 이렇게 트리를 만들면
1이 2의 자식노드가 아니라 4의 자식노드로 만들어진다.
너무 생각없이 푸는것같다.. 그냥 BST 알고리즘을 잠깐 보고오는게 건강에 좋을듯 하다... 위지원 제발..생각좀 해.. it를 그만 두던지!!
아.. 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 delete(self, node: TreeNode, key: int)->TreeNode:
if node is None:
return None
else:
if node.val == key:
#4가지
if node.left and node.right: # 자식이 다있음 > 대체 노드 탐색
parent, child = node, node.right
while child.left:
parent, child = child, child.left
child.left = node.left
if parent != node: #위에 그림에서 설명했던 상황
parent.left = child.right
child.right = node.right
node = child
elif node.left or node.right: # 자식이 둘중 하나만 있음
node = node.left or node.right
else: #자식이 없음
node = None
if node.val > key:
self.delete(node.left, key)
else:
self.delete(node.right, key)
return node
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
return self.delete(root, key)
tree가 바뀌질 않는다 delete 함수 내에서 바뀌고..?
Discuss를 보고 다음과 같은 상황을 알았다. node의 left right를 변경하는거니까 따라가게 경로처럼.. 아!>!
if node.val > key:
node.left = self.delete(node.left, key)
else:
node.right = self.delete(node.right, key)class Solution:
def delete(self, node: TreeNode, key: int)->TreeNode:
if node is None:
return None
else:
if node.val == key:
#4가지
if node.left and node.right: # 자식이 다있음 > 대체 노드 탐색
parent, child = node, node.right
while child.left:
parent, child = child, child.left
child.left = node.left
print(child.left.val)
if parent != node:
parent.left = child.right
child.right = node.right
node = child
print(node.val)
elif node.left or node.right: # 자식이 둘중 하나만 있음
node = node.left or node.right
else: #자식이 없음
node = None
return node
if node.val > key:
node.left = self.delete(node.left, key)
else:
node.right = self.delete(node.right, key)
return node
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
return self.delete(root, key)