꿀잠

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/maximum-depth-of-binary-tree/description/

트리의 깊이를 찾는 문제이다. 트리의 깊이를 찾기 위해 노드를 순차적으로 탐색해야 한다.
탐색하기 위해 Queue를 사용했으며, 노드를 Queue에 삽입할 때 현재의 깊이를 기준으로 1 추가하여 주었고, left 와 right가 null 이 아닌것을 체크하여 Queue에 삽입하고 poll하며 깊이를 확인해 주었다.

/**  
 * 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; 
 *     } 
 * } 
 */  
 
import java.util.*;  
  
public class Solution {  
    public int maxDepth(TreeNode root) {  
        if(root == null) return 0;  
  
        Queue<Depth> que = new ArrayDeque<>();  
        Depth rootDepth = new Depth(root, 1);  
        que.add(rootDepth);  
        int answer = 0;  
  
        while(!que.isEmpty()){  
            Depth curDepth = que.poll();  
            int depth = curDepth.depth;  
            TreeNode cur = curDepth.node;  
            answer = Math.max(depth, answer);  
  
            if(cur.left != null){  
                Depth nextLeftDepth = new Depth(cur.left, depth + 1);  
                que.add(nextLeftDepth);  
            }  
  
            if(cur.right != null){  
                Depth rightLeftDepth = new Depth(cur.right, depth + 1);  
                que.add(rightLeftDepth);  
            }  
        }  
  
        return answer;  
    }  
  
    private class Depth{  
        TreeNode node;  
        int depth;  
  
        Depth(TreeNode node, int depth){  
            this.node = node;  
            this.depth = depth;  
        }  
    }  
}