二叉树序列化 & 反序列化

本文介绍二叉树的序列化以及反序列化的方法

分别从先序遍历、后序遍历、层次遍历三个角度总结

⚠️ 不可以利用中序遍历实现序列化和反序列化 原因：无法得到根节点的位置

先序遍历

/**
 * @Description: 序列化 & 反序列化 先序遍历
 * @Author: LFool
 * @Date: 2021/12/31 18:40
 **/
public class CodecPreOrder {

    private String SEP = ",";
    private String NULL = "#";

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

    /**
     * Decodes your encoded data to tree.
     * @param data data
     * @return TreeNode
     */
    public TreeNode deserialize(String data) {
        LinkedList<String> nodes = new LinkedList<>();
        for (String s : data.split(SEP)) {
            nodes.addLast(s);
        }
        return deserialize(nodes);
    }

    /**
     * Encodes Helper
     * @param root root
     * @param sb result string
     */
    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return ;
        }
        sb.append(root.value).append(SEP);
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    /**
     * Decodes Helper
     * @param nodes node list
     * @return TreeNode
     */
    private TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) {
            return null;
        }
        String first = nodes.removeFirst();
        if (NULL.equals(first)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}

后序遍历

/**
 * @Description: 序列化 & 反序列化 后序遍历
 * @Author: LFool
 * @Date: 2022/1/20 00:53
 **/
public class CodecPostOrder {

    private String SEP = ",";
    private String NULL = "#";

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

    /**
     * Decodes your encoded data to tree.
     * @param data data
     * @return TreeNode
     */
    public TreeNode deserialize(String data) {
        java.util.LinkedList<String> nodes = new java.util.LinkedList<>();
        for (String s : data.split(SEP)) {
            nodes.addLast(s);
        }
        return deserialize(nodes);
    }

    /**
     * Encodes Helper
     * @param root root
     * @param sb result string
     */
    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return ;
        }
        serialize(root.left, sb);
        serialize(root.right, sb);
        sb.append(root.value).append(SEP);
    }

    /**
     * Decodes Helper
     * @param nodes node list
     * @return TreeNode
     */
    private TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) {
            return null;
        }
        String last = nodes.removeLast();
        if (NULL.equals(last)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(last));
        // 注意顺序 先 right 再 left
        root.right = deserialize(nodes);
        root.left = deserialize(nodes);
        return root;
    }
}

层次遍历

/**
 * @Description: 序列化 & 反序列化 层次遍历
 * @Author: LFool
 * @Date: 2022/1/20 01:13
 **/
public class CodecLayerOrder {

    private String SEP = ",";
    private String NULL = "#";

    /**
     * Encodes a tree to a single string.
     * @param root root
     * @return String
     */
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            if (cur == null) {
                sb.append(NULL).append(SEP);
            } else {
                sb.append(cur.value).append(SEP);
                q.offer(cur.left);
                q.offer(cur.right);
            }
        }
        return sb.toString();
    }

    /**
     * Decodes your encoded data to tree.
     * @param data data
     * @return TreeNode
     */
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        String[] nodes = data.split(SEP);
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        for (int i = 1; i < nodes.length; ) {
            TreeNode parent = q.poll();
            String left = nodes[i++];
            if (!NULL.equals(left)) {
                parent.left = new TreeNode(Integer.parseInt(left));
                q.offer(parent.left);
            } else {
                parent.left = null;
            }
            String right = nodes[i++];
            if (!NULL.equals(right)) {
                parent.right = new TreeNode(Integer.parseInt(right));
                q.offer(parent.right);
            } else {
                parent.right = null;
            }
        }
        return root;
    }
}