리트코드) 297. 이진 트리 직렬화 & 역직렬화(자바)

이진 트리 직렬화 & 역직렬화

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

문제 : 이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능 구현하라.

• 직렬화 TreeNode -> String
• 역직렬화 Stirng -> TreeNode

입출력

입력: root = [1,2,3,null,null,4,5]
출력: [1,2,3,null,null,4,5]

풀이

bfs를 사용하여 직렬화와 역직렬화를 구현하였다.
큐를 사용하여 동작을 반복한다.

역직렬화 부분이 약간 헷갈렸는데,
1) String 배열에 Split해서 값 셋팅
2) TreeNode Queue에 new TreeNode로 root 넣고 시작
3) 큐의 root 빼서 왼쪽, 오른쪽 값 채워서 큐에 넣기
.. 반복(큐가 비어있을 때 까지)

큐를 사용하지 않고 for 반복문으로 왼쪽 오른쪽 입력을 하면 될 것 같지만 깊이를 내려가지 않는다면 제자리를 반복하게 될 수 있다.
TreeNode로 구성된 Queue를 사용하여 사용했던 트리의 왼쪽 오른쪽을 넣었다가, 다시 빼서 하위의 왼쪽 오른쪽 값을 넣는 식으로 깊이를 내려가도록 한다.

트리 구조의 구성을 생각해보도록 하는 문제였다.

import java.util.*;
public class Codec {

    // 직렬화
    public String serialize(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if(root == null) {
           return ""; 
        }
        String result = String.valueOf(root.val);
        q.add(root);
        while(!q.isEmpty()) {
           TreeNode tree = q.poll();
           if(tree != null) {
               if(tree.left != null) {
                    q.add(tree.left);
                    result += ","+tree.left.val;
               } else {
                    result += ",null";
               }
               if(tree.right != null) {
                    q.add(tree.right);
                    result += ","+tree.right.val;
               } else {
                    result += ",null";
               }
            }   
        }
        return result;
    }

    // 역직렬화
    public TreeNode deserialize(String data) {
        if("".equals(data)) {
            return null;
        }
        Queue<TreeNode> q = new LinkedList<>();
        String[] str = data.split(",");
        
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        q.add(root);
        int idx = 1;
        while(!q.isEmpty()) {
            TreeNode tree = q.poll();
            if(!"null".equals(str[idx])) {
                tree.left = new TreeNode(Integer.parseInt(str[idx]));
                q.add(tree.left);
            }
            idx += 1;
            if(!"null".equals(str[idx])) {
                tree.right = new TreeNode(Integer.parseInt(str[idx]));
                q.add(tree.right);
            }
            idx+=1;
        }
        return root;
    }
}