leetcode 297

본 풀이는 정리 목적을 위해 작성했습니다.
본 문제는 treenode들을 serialize 후 해당 값을 deserialize하는 과정을 거치는 문제입니다.
먼저 serialize 방식을 살펴보겠습니다.

root = [1,2,3,null,null,4,5]

leetcode 예제에 있는 input을 예시로 생각해보면서 저는 string 값들을 ,로 join 후 나중에 리스트로 반환시켜 deserialize에 쓰기로 생각했습니다. 그리고 트리의 특징 중 하나인, 리스트 내의 indexing 방법이 $2*index$, $2 * index+1$로 child node를 접근하기 때문에 queue 방식을 못 사용했습니다.

따라서 위 추론을 기반으로 이 문제를 해결하기엔 리스트가 맞다고 판단했습니다.

result_string= '1,2,3,null,null,4,5,null,null,null,null'

serialize를 거치면 위와 같이 나옵니다. 이때, 뒤에 null은 불필요한 정보가 아니기에 따로 slice해주지 않았습니다. 이 string은 deserialize에 들어간다고 생각하시고 한 번 손으로 직접 과정을 따라가보시는 걸 추천드립니다.

deserialize 과정에서 child node 인덱싱을 $2*index$, $2 * index+1$ 으로 진행함으로써 기존 트리 형태를 만들 수 있었습니다. 제가 slicing으로 뒤에 연속적으로 오는 null 값들을 제거했던 경우에는, 4와 5는 3의 child node인데 잘못 인덱싱되어 오류를 범했습니다. 이 점 참고하셔서 제 코드를 봐주시면 감사하겠습니다! :)

import collections
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        result = list()
        nodequeue = collections.deque()
        nodequeue.append(root)
        def levelorder(root):
            
            while nodequeue:
                node = nodequeue.popleft()
                if node:
                    result.append(str(node.val))
                else:
                    result.append('null')
                    continue
                nodequeue.append(node.left)
                nodequeue.append(node.right)
        levelorder(root)

        
        
        result_str = ','.join(result) # string으로 변환 
        print(result_str) # 중간 점검 
        return result_str # return string 

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        data = data.split(',')
        data = ["F"] + data # 트리의 인덱스를 위해서 1번째 index부터 접근하게 했습니다. 'F'는 신경 안쓰시면 됩니다.
        idx = 1 # idx는 현재 노드의 위치를 나타내기 위해서 쓰이며, child node에 접근하고자 쓰입니다.  
        # print(data) # 중간 점검용 
        if data[1] == 'null' or data[1] == '': # 만약 아무것도 없는 트리라면
            return None 
        root = TreeNode(None) # 일단 초기화 진행합니다. 
        def buildTree(data,root,idx):
            
            if len(data) <= idx:
                return 
            root = TreeNode(data[idx])
            if 2*idx < len(data):
                root.left = buildTree(data, root.left,2*idx)
            if 2*idx < len(data):
                root.right = buildTree(data, root.right, 2*idx+1)
            return root 
                
        root = buildTree(data,root,idx)    
        return root