[LeetCode 297] Serialize and Deserialize Binary Tree (Java)

🚀 문제 분석

• 목표: 이진 트리를 하나의 문자열로 직렬화(Serialize)하고, 그 문자열을 다시 원래의 트리 구조로 역직렬화(Deserialize)합니다.
• 핵심: 트리의 계층 구조와 null 데이터를 손실 없이 저장하여 복원 시 원래의 부모-자식 관계를 유지해야 합니다.
• 전략: BFS (Level-order Traversal)를 사용하여 레벨 단위로 노드를 처리합니다.

💡 해결 전략: BFS를 이용한 레벨 순서 직렬화

1. 직렬화 (Serialize)

• Queue에 루트를 넣고 시작하여, 자식 노드가 null이더라도 문자열에 ,null을 명시적으로 추가합니다.
• 모든 노드를 레벨 순서대로 방문하며 StringBuilder에 누적합니다.

2. 역직렬화 (Deserialize)

• 직렬화된 문자열을 , 기준으로 분리하여 배열로 만듭니다.
• Queue에는 현재 '자식을 붙여줘야 할 부모 노드'들을 순서대로 담습니다.
• 배열의 인덱스(idx)를 하나씩 증가시키며, null이 아닐 경우에만 노드를 생성해 부모의 left와 right에 연결합니다.

💻 구현 코드 (Java)

public class Codec {
    // 트리를 문자열로 변환 (BFS)
    public String serialize(TreeNode root) {
        if (root == null) return "";

        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        sb.append(root.val);

        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            // 왼쪽 자식 처리
            if (node.left != null) {
                q.add(node.left);
                sb.append(",").append(node.left.val);
            } else {
                sb.append(",null");
            }
            // 오른쪽 자식 처리
            if (node.right != null) {
                q.add(node.right);
                sb.append(",").append(node.right.val);
            } else {
                sb.append(",null");
            }
        }
        return sb.toString();
    }

    // 문자열을 다시 트리로 복원
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        if (split.length == 0 || split[0].isBlank() || split[0].equals("null")) return null;

        int idx = 0;
        TreeNode root = new TreeNode(Integer.valueOf(split[idx++]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty() && idx < split.length) {
            TreeNode node = q.poll();

            // 왼쪽 자식 연결
            if (idx < split.length && !split[idx].equals("null")) {
                node.left = new TreeNode(Integer.valueOf(split[idx]));
                q.add(node.left);
            }
            idx++;

            // 오른쪽 자식 연결
            if (idx < split.length && !split[idx].equals("null")) {
                node.right = new TreeNode(Integer.valueOf(split[idx]));
                q.add(node.right);
            }
            idx++;
        }
        return root;
    }
}

🧐 기술적 고찰

• BFS vs DFS: DFS(전위 순회)로도 풀 수 있지만, BFS는 트리의 높이가 낮을 때 상대적으로 직관적인 레벨 구조를 보여줍니다. 팀장님 코드는 Queue를 활용해 BFS의 장점을 잘 살렸습니다.
• 데이터 무결성: 자식 노드가 없는 경우에도 null을 명시적으로 기록했기 때문에, 역직렬화 시 idx만으로도 정확한 부모-자식 위치를 찾아갈 수 있습니다.
• 시간 및 공간 복잡도: 모든 노드를 한 번씩 방문하므로 $O(N)$의 시간 복잡도를 가지며, 문자열과 큐를 저장하기 위해 $O(N)$의 공간을 사용합니다.