二叉树的序列化

二叉树的序列化：前、中、后、层序遍历实现

1. 前序遍历方法

• 序列化的时候被分成三部分（左 -> 右）：根节点、左子树、右子树
• 因此反序列化用队列
• （一般来说，还原二叉树需要前序+中序/后序+中序，由于node包含所有节点的信息，包括空指针的信息，因此可以直接还原）

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

public void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append("null,");
        return;
    }

    // 前序遍历位置
    sb.append("" + root.val + ",");

    serialize(root.left, sb);
    serialize(root.right, sb);        
}

public TreeNode deserialize(String data) {

    LinkedList<String> nodes = new LinkedList<>();

    for (String node : data.split(",")) {
        nodes.offer(node);
    }

    return deserialize(nodes);
}

public TreeNode deserialize(LinkedList<String> nodes) {
    if (nodes.isEmpty()) {
        return null;
    }

    // 前序遍历位置
    String node = nodes.poll();
    if ("null".equals(node)) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(node));

    root.left = deserialize(nodes);
    root.right = deserialize(nodes);

    return root;
}
复制代码

2. 后序遍历方法

• 后序遍历的序列化时候，只需把append放到后序遍历的位置去，因此序列化的顺序也改变了
• 被分成三部分（左 -> 右）：左子树、右子树、根节点
• 因此反序列化用栈
• 反序列化的时候，我们还是要先获取根节点，然后是右子树、最后才是左子树

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

public void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append("null,");
        return;
    }

    serialize(root.left, sb);
    serialize(root.right, sb);        

    // 后序遍历位置
    sb.append("" + root.val + ",");
}

public TreeNode deserialize(String data) {

    LinkedList<String> nodes = new LinkedList<>();

    for (String node : data.split(",")) {
        nodes.push(node);
    }

    return deserialize(nodes);
}

public TreeNode deserialize(LinkedList<String> nodes) {
    if (nodes.isEmpty()) {
        return null;
    }

    // 后序遍历位置
    String node = nodes.pop();
    if ("null".equals(node)) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(node));

    root.right = deserialize(nodes);
    root.left = deserialize(nodes);

    return root;
}
复制代码

3. 中序遍历方法

• 我们不能通过中序遍历将字符串反序列化成一颗二叉树，前序遍历根节点在第一个，后序遍历根节点在最后一个，二中序遍历根节点在中间
• 但是可以进行序列化

public void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append("null,");
        return;
    }

    serialize(root.left, sb);
    // 中序遍历位置
    sb.append("" + root.val + ",");
    serialize(root.right, sb);        
}
复制代码

4. 层序遍历方法

• 序列化同样按照层序遍历，利用队列遍历每一层节点，然后序列化到字符串中去
• 反序列化的时候同样也是用队列进行层序遍历的，因为空指针也被记录进去，所以要用i记录子节点的位置，不管子节点是不是空的，都要先获取判断一下

public String serialize(TreeNode root) {
    if (root == null) {
        return "";
    }

    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();

        if (node == null) {
            sb.append("null,");
            continue;
        }

        sb.append("" + node.val + ",");

        queue.offer(node.left);
        queue.offer(node.right);
    }

    return sb.toString();
}

public TreeNode deserialize(String data) {
    if ("".equals(data) || data.length() == 0) {
        return null;
    }

    String[] nodes = data.split(",");
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    for (int i = 1; i < nodes.length;) {
        // 先出队，获取节点
        TreeNode node =  queue.poll();

        // 左子树
        String left = nodes[i++];
        if ("null".equals(left)) {
            node.left = null;
        } else {
            node.left = new TreeNode(Integer.parseInt(left));
            queue.offer(node.left);
        }

        // 右子树
        String right = nodes[i++];
        if ("null".equals(right)) {
            node.right = null;
        } else {
            node.right = new TreeNode(Integer.parseInt(right));
            queue.offer(node.right);
        }
    }

    return root;
}
复制代码