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

数据结构与算法

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

序列化是容易的，序列化的关键在于空节点的处理，空节点也需要记录，我们可以用"#"代表空节点，用","进行节点之间的分隔
序列化和反序列化可以用前序、后序和层次遍历，但是注意中序遍历序列化是不行的，不同的树中序序列化之后可能一样，同时也无法反序列化，因为无法知道根节点。比如如下两棵树：

虽然两棵树并不一样，但是中序序列化的结果却一样。

前序序列化与反序列化的代码：

public String serialize(TreeNode root) {
    if (root == null) {
        return "#,";
    }
    String result = root.val + ",";
    result += serialize(root.left);
    result += serialize(root.right);
    return result;
}
public TreeNode deserialize(String data) {
    if (data == null || data.isEmpty()) {
        return null;
    }
    Queue<String> nodes = new LinkedList<>();
    for (String str : data.split(",")) {
        if (!str.isEmpty()) {
            nodes.add(str);
        }
    }
    return deserialize(nodes);
}
// 反序列化递归的关键相信递归函数，我们每次从队列中取出头元素构造根节点，剩下的子树构造交给递归函数去解决
private TreeNode deserialize(Queue<String> nodes) {
    if (nodes.isEmpty()) {
        return null;
    }
    String str = nodes.poll();
    if ("#".equals(str)) {
        return null;
    }
    int val = Integer.parseInt(str);
    TreeNode root = new TreeNode(val);
    root.left = deserialize(nodes);
    root.right = deserialize(nodes);
    return root;
}

后续序列化与反序列化的代码：

public String serialize(TreeNode root) {
    if (root == null) {
        return ",#";
    }
    String result = "";
    result += serialize(root.left);
    result += serialize(root.right);
    return result + "," + root.val;
}
public TreeNode deserialize(String data) {
    if (data == null || data.isEmpty()) {
        return null;
    }
    Stack<String> nodes = new Stack<>();
    for (String str : data.split(",")) {
        if (!str.isEmpty()) {
            nodes.push(str);
        }
    }
    return deserialize(nodes);
}
public TreeNode deserialize(Stack<String> nodes) {
    if (nodes.isEmpty()) {
        return null;
    }
    String str = nodes.pop();
    if ("#".equals(str)) {
        return null;
    }
    int val = Integer.parseInt(str);
    TreeNode root = new TreeNode(val);
    // 后序遍历要先右子树，再左子树
    root.right = deserialize(nodes);
    root.left = deserialize(nodes);
    return root;
}

层次序列化和反序列化：

public String serialize(TreeNode root) {
    if (root == null) {
        return null;
    }
    Queue<TreeNode> nodes = new LinkedList<>();
    nodes.add(root);
    StringBuilder sb = new StringBuilder();
    while (!nodes.isEmpty()) {
        TreeNode current = nodes.poll();
        if (current == null) {
            sb.append("#,");
            continue;
        }
        sb.append(current.val).append(",");
        nodes.add(current.left);
        nodes.add(current.right);
    }
    return sb.toString();
}
public TreeNode deserialize(String data) {
    if (data == null || data.isEmpty()) {
        return null;
    }
    String[] nodes = data.split(",");
    return deserialize(nodes);
}
private TreeNode deserialize(String[] nodes) {
    if (nodes == null || nodes.length == 0 || "#".equals(nodes[0])) {
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
    queue.add(root);
    int i = 1;
    while (i < nodes.length - 1 && !queue.isEmpty()) {
        TreeNode current = queue.poll();
        String leftStr = nodes[i++];
        if ("#".equals(leftStr)) {
            current.left = null;
        } else {
            TreeNode left = new TreeNode(Integer.parseInt(leftStr));
            current.left = left;
            queue.add(left);
        }
        String rightStr = nodes[i++];
        if ("#".equals(rightStr)) {
            current.right = null;
        } else {
            TreeNode right = new TreeNode(Integer.parseInt(rightStr));
            current.right = right;
            queue.add(right);
        }
    } 
    return root;
}

顺便提一下，leetcode中的树都是用层次序列化的方式存储的