꿀잠

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

주어진 트리 노드의 정보를 String의 형태로 변환하는 메서드, 그리고 그 String 으로 다시 노드를 만드는 메서드를 완성 시키는 문제이다. 다른 노드 간에도 같은 값이 같은 경우도 있었기에 값 뿐만 아니라 id가 필요하다고 생각하였고, id와 value 값, 그리고 노드 정보와 연결 정보를 분리하여 구현하였다. 각 값들을 분리하기 위하여 별도의 구간 분리 문자를 사용하였다. 최종 코드는 다음과 같다.

import java.util.*;  
  
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {  
  
    static String NULL_VALUE_STR = "null";  
    static String SEPARATOR = "/";  
    static String SEPARATOR_VALUE = ",";  
    static String SEPARATOR_PART = "~";  
  
    // Encodes a tree to a single string.  
    public String serialize(TreeNode root) {  
        if(root == null) return NULL_VALUE_STR;  
  
        Queue<Object[]> q = new ArrayDeque<>();  
        int id = 0;  
        q.add(new Object[]{root, id++});  
  
        StringBuilder sbValue = new StringBuilder();  
        StringBuilder sbFormation = new StringBuilder();  
  
        while(!q.isEmpty()){  
            Object[] rootInfo = q.poll();;  
            TreeNode node = (TreeNode)rootInfo[0];  
            int nodeId = (int)rootInfo[1];  
  
            sbValue.append(nodeId);  
            sbValue.append(SEPARATOR_VALUE);  
            sbValue.append(node.val);  
            sbValue.append(SEPARATOR);  
  
            sbFormation.append(nodeId);  
            sbFormation.append(SEPARATOR_VALUE);  
            int leftId = id++;  
            sbFormation.append(leftId);  
            sbFormation.append(SEPARATOR_VALUE);  
            int rightId = id++;  
            sbFormation.append(rightId);  
            sbFormation.append(SEPARATOR);  
  
            if(node.left != null){  
                q.add(new Object[]{node.left, leftId});  
            }  
            if(node.right != null){  
                q.add(new Object[]{node.right, rightId});  
            }  
        }  
        sbFormation.deleteCharAt(sbFormation.length() - 1);  
        sbValue.deleteCharAt(sbValue.length() - 1);  
        String result = sbValue.toString() + SEPARATOR_PART + sbFormation.toString();  
        return result;  
    }  
  
    // Decodes your encoded data to tree.  
    public TreeNode deserialize(String data) {  
        if(data.equals(NULL_VALUE_STR)){  
            return null;  
        }  
  
        String[] info = data.split(SEPARATOR_PART);  
        String nodeValues = info[0];  
        String nodeFormations = info[1];  
        String[] nodeIdValueArr = nodeValues.split(SEPARATOR);  
        String[] rootInfo = nodeIdValueArr[0].split(SEPARATOR_VALUE);  
        String rootKey = rootInfo[0];  
  
        Map<String, TreeNode> nodes = new HashMap<>();  
  
        for(String nodeIdValue: nodeIdValueArr){  
            String[] idValue = nodeIdValue.split(SEPARATOR_VALUE);  
            String id = idValue[0];  
            String value = idValue[1];  
            nodes.put(id, new TreeNode(Integer.parseInt(value)));  
        }  
  
        String[] nodeFormationArr = nodeFormations.split(SEPARATOR);  
        for(String nodeForamtion: nodeFormationArr){  
            String[] formation = nodeForamtion.split(SEPARATOR_VALUE);  
            String main = formation[0];  
            String left = formation[1];  
            String right = formation[2];  
            TreeNode mainNode = nodes.get(main);  
  
            if(nodes.containsKey(left)){  
                mainNode.left = nodes.get(left);  
            }  
  
            if(nodes.containsKey(right)){  
                mainNode.right = nodes.get(right);  
            }  
        }  
  
        return nodes.get(rootKey);  
    }  
}  
  
// Your Codec object will be instantiated and called as such:  
// Codec ser = new Codec();  
// Codec deser = new Codec();  
// TreeNode ans = deser.deserialize(ser.serialize(root));

문자열에서 객체를 만드는 메서드에서 맵을 이용하면 쉽게 구현할 수 있다고 생각했지만 꽤나 코드가 길어져 버렸다. 통과 후 다른 사람의 코드를 보았다. deserialize 할 때에도 Queue 를 사용한다면 값 분리도 단순하게 공백으로만 할 수 있었다. deserialize를 너무 어렵게 생각 했었던 것 같다. 아래는 통과 후 참고한 다른 해답 코드이다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null) return "null";
        StringBuilder sb = new StringBuilder();

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr==null){
                sb.append("null ");
                continue;
            }
            sb.append(curr.val).append(" ");
            //no null check for left and right so that we can get null in our string.
            q.offer(curr.left);
            q.offer(curr.right);
        }
        return sb.toString();
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("null")) return null;

        String[] nodes = data.split(" "); //split using space to get the individual nodes

        //root using 0th string
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> parentQ = new LinkedList<>();
        //add root as 1st parent
        parentQ.offer(root);

        for(int i=1;i<nodes.length;i++){
            TreeNode parent = parentQ.poll();
            //we handle left and right child of i-1th node
            if(!nodes[i].equals("null")){
                TreeNode leftChild = new TreeNode(Integer.parseInt(nodes[i]));
                parent.left = leftChild; //assign to parent
                parentQ.offer(leftChild); //add child to parentQ for next iteration
            }
            if(!nodes[++i].equals("null")){
                TreeNode rightChild = new TreeNode(Integer.parseInt(nodes[i]));
                parent.right = rightChild;
                parentQ.offer(rightChild);
              //  i=i+1;
            }
        }
        return root;
        
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));