꿀잠

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-maximum-path-sum/

주어진 이진 트리 노드를 하나의 길로 연결 했을 때 가장 큰 누적 합의 값을 찾는 문제이다.

특정 노드에서 길을 잇기 위해선 좌우 노드와 이어지거나, 좌 또는 우 노드 중 하나와 상위 노드와의 연결이 되는 경우이다. 이러한 규칙으로 재귀적으로 순환하며 특정 노드에서 좌,우 노드와의 합계의 최대 값을 결과 값으로 구할 수 있다.

아래는 통과된 코드이다. 주의할 점은 return 해서 상위 노드로 보내는 값과 해당 노드에서 가능한 최대 값의 계산 방식이 다르다는 점이다.

class Solution {  
  
    int answer;  
  
    public int maxPathSum(TreeNode root) {  
        this.answer = Integer.MIN_VALUE;  
        recursiveNode(root);  
        return answer;  
    }  
  
    public int recursiveNode(TreeNode root){  
  
        if(root == null) return 0;  
  
        int val1 = root.val;  
        int val2 = Math.max(recursiveNode(root.left), 0);  
        int val3 = Math.max(recursiveNode(root.right), 0);  
  
        int maxValue = val1 + val2 + val3;  
        answer = Math.max(maxValue, answer);  
  
        return val1 + Math.max(val2, val3);  
    }  
}

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

이진 트리에서 두 노드의 공통 조상 중 가장 가까운 공통 조상을 찾는 문제이다.

이진트리의 경우 좌측 노드는 현재의 값보다 작으며 우측 노드는 현재의 값보다 크다는 특징이 있다. 특정 두 노드의 공통 조상 중 가장 가까운 조상일 경우 해당 노드를 기준으로 좌, 우측에 두 노드가 있게 된다. 따라서 해당 조건으로 루트에서 노드를 따라 찾아가면 찾을 수 있다.

/**  
 * Definition for a binary tree node. * public class TreeNode { 
   *     int val; 
   *     TreeNode left; 
   *     TreeNode right; 
   *     TreeNode(int x) { val = x; } 
   * } 
   */  
class Solution {  
  
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
        int pVal = p.val;  
        int qVal = q.val;  
  
        while(root != null){  
            int curVal = root.val;  
            // 두 값 모두 현재 노드에서 왼쪽에 있는 경우.
            if(curVal > pVal && curVal > qVal){  
                root = root.left;  
			// 두 값 모두 현재 노드에서 오른쪽에 있는 경우.
            }else if(curVal < pVal && curVal < qVal){  
                root = root.right;  
            }else{  
                return root;  
            }  
        }  
  
        return 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;  
        }  
    }  
}

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에 새로 넣기 때문에 하나의 레벨을 빼내기 전에 사이즈를 체크해서 꺼내면 된다.