리트코드 297번 Serialize and Deserialize Binary Tree (Python)

Problem

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Solution

# Definition for a binary tree node.
from collections import deque
from typing import Optional

class Codec:
    def serialize(self, root) -> str:
        answer = []
        dq = deque([root])
        while dq:
            node = dq.popleft()

            if node is None:
                answer.append(None)
            else:
                answer.append(node.val)
                dq.append(node.left)
                dq.append(node.right)

        return ' '.join(str(x) for x in answer)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        data_list = deque(None if x == "None" else int(x) for x in data.split())
        root_v = data_list.popleft()
        if root_v is None:
            return None

        root = TreeNode(root_v)
        node_q = deque([root])
        
        while node_q and data_list:
            node = node_q.popleft()
            left_val = data_list.popleft()
            right_val = data_list.popleft()
            
            if left_val is not None:
                left_node = TreeNode(left_val)
                node.left = left_node
                node_q.append(left_node)
                
            if right_val is not None:
                right_node = TreeNode(right_val)
                node.right = right_node
                node_q.append(right_node)

        return root

bfs를 응용하여 depth를 하나씩 들어가며 해당 depth의 노드를 탐색하였다.

Reference

파이썬 알고리즘 인터뷰 47번