297. Serialize and Deserialize Binary Tree

Serialize , Deserialize

- 결국 Tree를 순회해서 -> 배열 모양의 String으로 만들거나 (Serialize)

 - 배열 모양의 String을 각각의 원소들로 parsing 한 배열로 만들 후, 이 배열을 순회하면서 Binary Tree 자료구조에 Binding 하는 것이다. (Deserialize)

여기서 나는, 각각에 대해 BFS 방법을 사용하고자 한다.

Serialize 에서는,

- Tree 를 BFS로 Queue에 먼저 넣어두고, Queue에서 값을 빼서 ArrayList에 넣어준다.(단, 현재 node가 null이면, null을 arrayList에 넣어준다.)
- 이렇게 만든 ArrayList를 string으로 직렬화

Deserialize 에서는

- Queue 자료구조에 들어갈 데이터 타입을 TreeNode 로 해둬야한다. (이렇게 만들어야, 현재 queue에서 빼낸 currNode의 left, right 노드를 queue에 넣을수있음)
- queue에 넣을 때 배열 index 범위를 넘으면 안되니까, left, right 마다 index를 체크해줘야함

 

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<Integer> arr = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        
        q.add(root);
        
        while(!q.isEmpty()) {
            TreeNode currNode = q.poll();
            Integer currVal = currNode == null ? null : currNode.val;
            arr.add(currVal);
                
            if(currNode != null) {
                q.add(currNode.left);
                q.add(currNode.right);
            }
        }
        return arr.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        data = data.substring(1, data.length() -1);
        
        String[] arr = data.split(", ");
        if(arr.length == 0 || arr[0].equals("null")) return null;
        List<Integer> list = new ArrayList<>();
        for(String item : arr) {
            if(item.equals("null")) list.add(null);
            else list.add(Integer.valueOf(item));
        }
        
        TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        
        int index = 1;
        
        while(index < arr.length && !q.isEmpty()) {
            
            TreeNode curr = q.poll();
            if(list.get(index) != null && index < arr.length) {
                TreeNode left = new TreeNode(list.get(index));
                curr.left = left;
                q.add(left);
            }
            index++;
            if(list.get(index) != null && index < arr.length) {
                TreeNode right = new TreeNode(list.get(index));
                curr.right = right;
                q.add(right);
            }
            index++;
        }
        return root;
    }
}