[코테 연습] Delete Node in a BST Python

https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/553/week-5-august-29th-august-31st/3443/

Explore - LeetCode

---

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)