@TOC

剑指 Offer 37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

解题思路

做过一定数量二叉树题目的同学一定会发现，题目如果用数组形式表示一颗二叉树时，都是用层序遍历表示的，并且null也会给出，因为这样才好唯一确定一棵树。因此这里序列化我们也用层序遍历，为完整表示二叉树，考虑将叶节点下的 null也记录。在此基础上，对于列表中任意某节点 node ，其左子节点 node.left 和右子节点 node.right 在序列中的位置便是唯一确定的了。

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) return "null";

        //层序遍历，用“，”隔开每个元素，最后会多出一个“，”但是没什么关系。
       //因为反序列化时，用‘，’切分，自然就去掉最后的‘，’了
        queue.add(root);
        sb.append(root.val).append(",");
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur.left != null){
                queue.add(cur.left);
                sb.append(cur.left.val).append(",");
            }else{
                sb.append("null,");
            }
            if(cur.right != null){
                queue.add(cur.right);
                sb.append(cur.right.val).append(",");
            }else{
                sb.append("null,");
            }
        }
        //System.out.print(sb.toString());用于查看是否序列化成功
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(",");

        if(strs.length == 0 || strs[0].equals("null")) return null;

        TreeNode root = new TreeNode(Integer.valueOf(strs[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int index = 1;
        while(index < strs.length){
            TreeNode node = queue.poll();
            if (node != null) {//按照层序遍历特性，当前节点不是null的话，就从数组中读取两个值作为其左右子节点
                TreeNode left = strs[index].equals("null") ? null : new TreeNode(Integer.valueOf(strs[index]));
                index++;
                queue.add(left);
                node.left = left;

                TreeNode right = strs[index].equals("null") ? null : new TreeNode(Integer.valueOf(strs[index]));
                index++;
                queue.add(right);
                node.right = right;
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));