Leet code (Hard): 297. Serialize and Deserialize Binary Tree - Java

 

TreeNode 객체로 root 가 주어지면 주어진 두 메서드를 완성해서 serialize, deserialize 하여 입력 그대로의 root를 리턴하는 문제이다.

 

serialize 메서드는 String을 리턴해야해서 TreeNode를 돌며 노드를 String으로 붙여나가야하는데

String의 +보다 StringBuilder의 append()를 써서 붙여나가는 것이 훨~~~씬 더 빠르다.

String으로 + 하면서 붙이면 그때그때 계속 객체를 생성해야하기 때문..

 

deserialize 메서드는 String을 받아서 TreeNode를 리턴해야한다.

 

serialize, deserialize 둘 다 Queue를 사용했다.

 

/**
 * 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 "";

        StringBuilder output = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            
            if(node == null){
                output.append("#,");
            }else{
                output.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        
        return output.toString();
    }

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

        String[] tree = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(tree[0]));
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int child = 1;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();

            if(!tree[child].equals("#")){
                TreeNode left = new TreeNode(Integer.parseInt(tree[child]));
                node.left = left;
                queue.offer(left);
            }

            child++;

            if(!tree[child].equals("#")){
                TreeNode right = new TreeNode(Integer.parseInt(tree[child]));
                node.right = right;
                queue.offer(right);
            }

            child++;
        }

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