검지 Offer: 서열화 두 갈래 트리(java 버전)

제목 설명

분석

선착순으로 훑어보는 서열화

import java.util.*;
public class Solution {
    String Serialize(TreeNode root) { //  
        StringBuilder sb = new StringBuilder();
        if(root==null)
            return "#!";
        sb.append(root.val+"!");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
  }
    TreeNode Deserialize(String str) { //  
        String[] values = str.split("!");
        Queue<String> queue = new LinkedList<>();
        for(int i=0;i<values.length;i++){
            queue.offer(values[i]);
        }
        return buildTree(queue);
  }
    TreeNode buildTree(Queue<String> queue){ //  
        String value = queue.poll();
        if(value.equals("#"))
            return null;
        TreeNode head = new TreeNode(Integer.parseInt(value));
        head.left = buildTree(queue);
        head.right = buildTree(queue);
        return head;
    }
}

층차적으로 훑어보는 서열화

import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null)
            return "#!";
        queue.offer(root);
        StringBuilder sb = new StringBuilder();
        sb.append(root.val+"!");
        TreeNode temp;
        while(!queue.isEmpty()){
                temp = queue.poll();
                if(temp.left!=null){
                    sb.append(temp.left.val+"!");
                    queue.offer(temp.left);
                }else{
                    sb.append("#!");
                }
                if(temp.right!=null){
                    sb.append(temp.right.val+"!");
                    queue.offer(temp.right);
                }else{
                    sb.append("#!");
                }
       }
        return sb.toString();
  }
    TreeNode Deserialize(String str) {
        if(str==null || str.equals("#!"))
            return null;
        String[] values = str.split("!"); //  
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode temp;
        int index = 1;
        while(!queue.isEmpty() ){
            int len = 2;  //  2 
            temp = queue.poll();
            while(len>0){
                --len;
                if(values[index].equals("#")){ // ， 
                    index++;
                    continue;
                }
                if(index%2==1){ //  ， 
                    TreeNode node = new TreeNode(Integer.parseInt(values[index++]));
                    queue.offer(node);
                    temp.left=node;
                }else{ 
                    TreeNode node = new TreeNode(Integer.parseInt(values[index++]));
                    queue.offer(node);
                    temp.right=node;
                }
            }
        }
        return root;
   }
}

import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        if (root == null) {
            return "#!";
        }
        StringBuilder sb = new StringBuilder();
        sb.append(root.val + "!");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root.left != null) {
                sb.append(root.left.val + "!");
                queue.offer(root.left);
            } else {
                sb.append("#!");
            }
            if (root.right != null) {
                sb.append(root.right.val + "!");
                queue.offer(root.right);
            } else {
                sb.append("#!");
            }
        }
        return sb.toString();   
  }
    TreeNode Deserialize(String str) {
        String[] values = str.split("!");
        TreeNode head = generateNodeByString(values[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        int index = 1;
        if (head != null) {
            queue.offer(head);
        }
        TreeNode node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            node.left = generateNodeByString(values[index++]);
            node.right = generateNodeByString(values[index++]);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return head;
  }
  TreeNode  generateNodeByString(String val){
        if(val.equals("#"))
            return null;
        return new TreeNode(Integer.parseInt(val));
    }
}