37 序列化二叉树

序列化和反序列化二叉树，不止一种序列化方法。

前序遍历序列化：

public class SerializeTree {
 
    String Serialize(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        serialize(root,sb);
        return sb.toString();
    }

    private void serialize(TreeNode root, StringBuilder sb){
        if(root==null){
            sb.append("#,");
            return;
        } else {
            sb.append(root.val).append(",");
        }
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    int len;
    TreeNode Deserialize(String str) {
        String[] ss=str.split(",");
        len=ss.length;
        return deserialize(ss, -1);
    }
    TreeNode deserialize(String[] ss, int index){
        index++;
        if(index==len) return null;
        if("#".equals(ss[index])) return null;
        TreeNode root=new TreeNode(Integer.parseInt(ss[index]));
        root.left=deserialize(ss,index);
        root.right=deserialize(ss,index);
        return root;

    }

    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        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);
        StringBuilder sb=new StringBuilder();
        sb.append(root.val).append(",");
        while(!queue.isEmpty()){
            TreeNode t=queue.poll();

            if(t.left==null){
                sb.append("#,");
            } else {
                queue.add(t.left);
                sb.append(t.left.val).append(",");
            }
            if(t.right==null){
                sb.append("#,");
            } else {
                queue.add(t.right);
                sb.append(t.right.val).append(",");
            }
        }
        int end=sb.length()-1;
        while(true){
            char c=sb.charAt(end);
            if(c!=',' && c!='#') break;
            end--;
        }
        return sb.substring(0,end+1);
    }

    TreeNode Deserialize(String str) {
        if("#".equals(str)) return null;
        String[] ss=str.split(",");
        Queue<TreeNode> queue=new LinkedList<>();
        TreeNode root=new TreeNode(Integer.parseInt(ss[0]));
        queue.add(root);
        int index=1, len=ss.length;
        while(!queue.isEmpty()){
            if(index>=len) break;
            TreeNode t=queue.poll();
            if("#".equals(ss[index])){
                index++;
            } else {
                t.left=new TreeNode(Integer.parseInt(ss[index++]));
                TreeNode a=t.left;
                queue.add(t.left);
            }
            if(index>=len) break;
            if("#".equals(ss[index])){
                index++;
            } else {
                t.right=new TreeNode(Integer.parseInt(ss[index++]));
                TreeNode a=t.right;
                queue.add(t.right);
            }

        }
        return root;
    }
}