题解 | 序列化二叉树

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        //隔离空树
        if(root==null) return "{}";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int height = getHeight(root);
        Queue<Integer> res = new LinkedList<>();
        //层序遍历
        while(!queue.isEmpty()){
            TreeNode curNode = queue.poll();
            
            if(curNode==null){
                res.add(-1);
            }else{
                res.add(curNode.val);
                queue.add(curNode.left);
                queue.add(curNode.right);
            }

        }
        StringBuilder resStr = new StringBuilder();
        resStr.append("{");

        int buffer = 0; 
        while(!res.isEmpty()){
            int curVal = res.poll();
            if(curVal==-1){
                buffer++;
                
            }else{
                for(int i = 0;i<buffer;i++) resStr.append("#,");
                resStr.append(curVal);
                resStr.append(",");
                buffer = 0;
            }
        }
        resStr.deleteCharAt(resStr.length()-1);
        resStr.append("}");
        System.out.println(resStr);
        return resStr.toString();
    }
    int getHeight(TreeNode root){
        if(root==null) return 0;
        int height = 1 + Math.max(getHeight(root.left),getHeight(root.right));
        return height;        
    }



    TreeNode Deserialize(String str) {

        //隔离空树
        if(str.equals("{}")) return null;

        str = str.substring(1,str.length()-1);
        System.out.println(str);
        String[] strs = str.split(",");

        Queue<String> strQueue = new LinkedList<>();

        for(String s:strs) strQueue.add(s);
        
        TreeNode root = new TreeNode(Integer.valueOf(strQueue.poll()));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        while(!nodeQueue.isEmpty()&&!strQueue.isEmpty()){
            TreeNode curRoot = nodeQueue.poll();
            String left = strQueue.poll();
            String right = strQueue.poll();
            System.out.println(left+" "+right);
            if(left!=null&&!left.equals("#")) {
                curRoot.left = new TreeNode(Integer.valueOf(left));
                nodeQueue.add(curRoot.left);
            }
            if(right!=null&&!right.equals("#")){
                curRoot.right = new TreeNode(Integer.valueOf(right));
                nodeQueue.add(curRoot.right);
            } 
        }
        return root;
    }
}