力扣 297 二叉树的序列化与反序列化

题意：序列化和反序列化一个二叉树

思路：按层遍历

思想：树的按层遍历

复杂度：时间O（n)，空间O(n)

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return "";
        StringBuilder res = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        // 按层遍历获取string
        while(!q.isEmpty()) {
            TreeNode cur = q.poll();
            if(cur == null) {
                res.append(", ");
            } else {
                res.append(cur.val + " ");
                q.add(cur.left);
                q.add(cur.right);
            }
        }
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0)
            return null;
        String[] strs = data.split(" ");
        TreeNode res = new TreeNode(Integer.parseInt(strs[0]));
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(res);
        int cnt = 1;
        // 按层遍历，复原Tree
        while(!q.isEmpty()) {
            TreeNode cur = q.poll();
            if(!strs[cnt].equals(",")) {
                TreeNode temp = new TreeNode(Integer.parseInt(strs[cnt]));
                cur.left = temp;
                q.add(temp);
            }
            cnt++;
            if(!strs[cnt].equals(",")) {
                TreeNode temp = new TreeNode(Integer.parseInt(strs[cnt]));
                cur.right = temp;
                q.add(temp);
            }
            cnt++;
        }
        return res;
    }
}