二叉树的序列化与反序列化

LeetCode每日一题，297. Serialize and Deserialize Binary Tree

先看题目描述

大意就是要求实现二叉树的序列化与反序列化要求，没要求序列化出来的字符串格式

算法与思路

一开始以为非要按图中给的例子那种格式来序列化，想了半天没想出来，就去看题解，才发现只要能实现序列化与反序列化就行，格式能自己定，才想明白怎么做。序列化可以采用先序遍历的编码方式，就是先输出根节点，然后输出左子树，再输出右子树，反序列化就是将字符串分隔开得到元素列表，然后从左向右遍历，若当前元素为 none ，则当前为空树，否则先解析这个元素的左子树，再解析右子树。序列化算法用到了递归，使用了可变字符串 StringBuilder，反序列化算法也用到了递归，使用到了栈

算法源码

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

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

    public void buildString(TreeNode root, StringBuilder sb) {
        if (root == null) sb.append("none,");
        else {
            sb.append(String.valueOf(root.val)).append(",");
            buildString(root.left, sb);
            buildString(root.right, sb);
        }
    }


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }

    public TreeNode builTree(Deque<String> nodes) {
        if (nodes.peek().equals("none")) {
            nodes.pop();
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(nodes.pop()));
        root.left = builTree(nodes);
        root.right = builTree(nodes);
        return root;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Deque<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(",")));
        return builTree(nodes);
    }
}

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