Serialize and Deserialize Binary Tree - LeetCode

문제 접근 🤔

• serialize (직렬화)
  • DFS를 통해 모든 노드들을 탐색하며 각 노드 값을 리스트에 넣어준다.
  • 노드가 비어있을 경우 null 을 저장한다.
  • 구분자를 공백으로 하여 리스트를 조인한 문자열을 최종 반환한다.
• deserialize (역직렬화)
  - 입력값인 문자열을 공백을 구분자로 하여 리스트로 만들어 준 후, deque 으로 변환해준다.
  - DFS를 통해 순회하며 현재 덱의 맨 앞 요소부터 TreeNode 로 변환해준다.
  - 이때 직렬화되어 입력된 문자열이 깊이 우선 탐색되어 트리의 왼쪽 노드들부터 차례대로 담겨 있으므로, 역직렬화 할 때에도 트리의 왼쪽부터 차례로 채워나가야 한다.
  - 재귀함수의 리턴 값으로 노드를 반환하고 이 반환 값들을 각각 노드의 왼쪽 트리, 오른쪽 트리로 저장해준다.
  - 재귀 탐색의 최종 리턴 값인 노드를 반환해주면 직렬화한 문자열을 역직렬화한 트리가 반환된다.
  
  
  

놓쳤던 부분 😅

• 처음 짠 코드가 자꾸 오류 나고 헷갈려서 다른 분의 아이디어를 참고했다.
  
  
  

코드 😁

파이썬 코드(71 ms)

from collections import deque

class Codec:

    def serialize(self, root: TreeNode) -> str:
        data = []
        
        def dfs(node):
            if not node:
                data.append('null')
                return
        
            data.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        
        dfs(root)
        return ' '.join(data)

    def deserialize(self, data : str) -> TreeNode:
        dataQ = deque(data.split())

        def dfs(q):
            if not len(q):
                return
            
            val = q.popleft()
            if val == 'null':
                return None
            
            node = TreeNode(val)
            node.left = dfs(q)
            node.right = dfs(q)
            return node
        
        return dfs(dataQ)

자바스크립트 코드(295 ms)

const serialize = (root) => {
  const data = [];

  const dfs = (node) => {
    if (node === null) {
      data.push('null');
      return;
    }

    data.push(node.val);
    dfs(node.left);
    dfs(node.right);
  };

  dfs(root);
  return data.join(' ');
};

const deserialize = (data) => {
  dataList = data.split(' ');

  const dfs = (list) => {
    if (list.length === 0) {
      return;
    }

    const val = list.shift();
    if (val === 'null') {
      return null;
    }

    const node = new TreeNode(val);
    node.left = dfs(list);
    node.right = dfs(list);
    return node;
  };

  return dfs(dataList);
};