꿀잠

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));

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

주어진 커스텀 클래스인 이진트리 노드를 레벨에 따른 중첩 List배열로 반환하는 문제이다.

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

class Solution {  
    public List<List<Integer>> levelOrder(TreeNode root) {  
        List<List<Integer>> answer = new ArrayList<>();  
        if (root == null) {  
            return answer;  
        }  
  
        Queue<TreeNode> que = new ArrayDeque<>();  
        que.offer(root);  
  
        while (!que.isEmpty()) {  
            List<Integer> levelList = new ArrayList<>();  
            int queSize = que.size();  
  
            while (queSize-- > 0) {  
                TreeNode node = que.poll();  
                levelList.add(node.val);  
                if (node.left != null) {  
                    que.offer(node.left);  
                }  
  
                if (node.right != null) {  
                    que.offer(node.right);  
                }  
            }  
            if (levelList.size() > 0) {  
                answer.add(levelList);  
            }  
        }  
  
        return answer;  
    }
}

레벨 단위로 처리하기 위해서 Queue를 이용하였다. 하나의 레벨을 Queue 에 넣어 전부 꺼내며 리스트를 완성하고, 전부 꺼내는 동안 다음 레벨의 노드를 Queue에 넣어 순차적으로 레벨 List를 만들어 주었다. 하나의 레벨을 꺼내며 Queue에 새로 넣기 때문에 하나의 레벨을 빼내기 전에 사이즈를 체크해서 꺼내면 된다.