题解 | #Java序列化二叉树#

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 "#";
        
        // StringBuilder 拼接字符
        StringBuilder builder = new StringBuilder();
        builder.append(root.val + "");
        
        // 用层序遍历的方法遍历，借助队列保存每一层的节点
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
            // 每一轮循环先记录节点数目，避免被后面入队的节点影响
            int sz = q.size();
            
            for (int i=0; i < sz; i++) {
                TreeNode t = q.poll();
                
                // 节点不为空，则记录节点的值，用 “,” 分隔开
                if (t.left != null) {
                    q.offer(t.left);
                    builder.append("," + t.left.val);
                }
                // 节点为空，用 "#" 表示
                else {
                    builder.append(",#");
                }
                
                // 同样方法处理右节点
                if (t.right != null) {
                    q.offer(t.right);
                    builder.append("," + t.right.val);
                }
                else {
                    builder.append(",#");
                }
            }
        }

        return builder.toString();        
    }
    
    TreeNode Deserialize(String str) {
        // 根据 “,” 分隔各个值，返回值为 String 数组
        String[] source = str.split(",");
        
        // 第一个值就是 "#"，说明是空树
        if ("#".equals(source[0])) {
            return null;
        }
        
        // 层序遍历，重新生成了树
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.valueOf(source[0]));
        q.offer(root);
        
        // 记录 source 数组访问到了哪个下标
        int cnt = 1;
        
        while (!q.isEmpty()) {
            int sz = q.size();
            
            for (int i=0; i < sz; i++) {
                TreeNode t = q.poll();
                if ("#".equals(source[cnt])) {
                    t.left = null;
                }
                else {
                    t.left = new TreeNode(Integer.valueOf(source[cnt]));
                    q.offer(t.left);
                }
                cnt++;
                
                if ("#".equals(source[cnt])) {
                    t.right = null;
                }
                else {
                    t.right = new TreeNode(Integer.valueOf(source[cnt]));
                    q.offer(t.right);
                }
                cnt++;
            }
        }
        
        return root;
    }
}