题解 | #序列化二叉树#

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 sb = new StringBuilder();
        // 允许空节点入队
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            // 当前层的节点数
            int n = q.size();
            // 判断当前层是否为最后一层的下一层（全为空节点）, 是则结束，否则继续遍历
            int numOfNull = 0; // 空节点数
            for (TreeNode node : q) {
                if (node == null)
                    numOfNull++;
            }
            if (numOfNull == n) // 说明当前层全为空节点，结束
                break;
            // 遍历一层的节点
            for (int i = 0; i < n; i++) {
                root = q.poll();
                if (root == null) {
                    sb.append("#,");
                    q.offer(null);
                    q.offer(null);
                } else {
                    sb.append(Integer.toString(root.val) + ",");
                    q.offer(root.left);
                    q.offer(root.right);
                }
            }
        }
        // 比如：示例例结果为："1,2,3,#,#,6,7,"
        // 反序列化时：split(",")的结果数组里最后一个元素为7，即最后的逗号不影响分割结果，会自动将最后的空字符删除，具体可见split的源码
        return sb.toString();
    }
    TreeNode Deserialize(String str) {
        if ("".equals(str)) // 空树返回null
            return null;
        TreeNode head = null; // 反序列化后的树根
        String[] vals = str.split(",");
        // 需要一个存放树节点的列表，用来找到当前遍历节点的父节点，才能串联成树
        List<TreeNode> nodes = new ArrayList<>();
        // 初始化树根：
        head = parseTreeNode(vals[0]);
        nodes.add(head);
        // 从第2个节点开始遍历
        for (int i = 1; i < vals.length; i++) {
            TreeNode node = parseTreeNode(vals[i]);
            // 添加到nodes中：（空节点也要添加到nodes中，才能保持下标的正确性）
            nodes.add(node);
            if (node == null) { // 如果为空节点，则不需要与父节点串联了
                continue;
            }
            // 串联父子节点：
            // 节点i的父节点下标为：(i-1)/2
            TreeNode parentNode = nodes.get((i-1)/2);
            // 确定当前节点为父节点的 左 还是 右 孩子节点：
            // 下标i为奇数则为左孩子，为偶数则为右孩子
            if (i % 2 == 0) {
                parentNode.right = node;
            } else {
                parentNode.left = node;
            }
        }
        return head;
    }
    
    // 将字符串解析为二叉树节点
    public TreeNode parseTreeNode(String str) {
        TreeNode node = null;
        if ("#".equals(str)) {
            return null;
        } else {
            int val = Integer.parseInt(str);
            node = new TreeNode(val);
        }
        return node;
    }
}