算法练习(15)-设计1个二叉树的序列化与反序列化实现?

本文主要是介绍算法练习(15)-设计1个二叉树的序列化与反序列化实现?，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路: 二叉树的各种顺序中,随便挑1种,遍历每个节点, 拼装出1个字符串即可实现序列化。要注意的是, 空节点也需要, 可以找一个特殊符号比如#表示。 反序列化则是相反的过程,解析该字符串即可。

这里用层序遍历来实现一把:

序列化代码:

public static String serial(TreeNode node) {
    StringBuilder sb = new StringBuilder();
    if (node == null) {
        sb.append("#_");
        return sb.toString();
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(node);
    while (!queue.isEmpty()) {
        TreeNode n = queue.poll();
        sb.append(n == null ? "#_" : n.val + "_");
        if (n != null) {
            queue.add(n.left);
            queue.add(n.right);
        }
    }
    //注:0位置占位不用, 方便后面反序列化
    return "*_" + sb.toString();
}

假设有一颗树：

把空节点补全后，如下图：

序列化后为 *_1_2_3_4_5_#_7_#_#_#_#_#_#_ 按"_"拆分成String[]后，就变成了二叉树的数组存储 ， 如果根节点的下标从1算起，每个元素的左孩子索引为2*i，右孩子索引为2*i+1 ，它的父节点索引为i/2 （这也是为啥第0个元素要用*占位的原因），根据这个特性， 很容易可以写反序列化的代码：

public static TreeNode deSerial(String str) {
    if (str == null || str.length() <= 0) {
        return null;
    }
    String[] arr = str.split("_");
    TreeNode root = new TreeNode(Integer.parseInt(arr[1]));
    Map<Integer, TreeNode> parentMap = new HashMap<>();
    parentMap.put(1, root);
    int curr = 1;
    while (curr < (arr.length >> 1)) {
        int leftIndex = curr << 1;
        int rightIndex = (curr << 1) + 1;
        String leftVal = arr[leftIndex];
        String rightVal = arr[rightIndex];
        if (!"#".equals(leftVal)) {
            TreeNode leftNode = new TreeNode(Integer.parseInt(leftVal));
            int parentIndex = leftIndex >> 1;
            parentMap.get(parentIndex).left = leftNode;
            parentMap.put(leftIndex, leftNode);
        }
        if (!"#".equals(rightVal)) {
            TreeNode rightNode = new TreeNode(Integer.parseInt(rightVal));
            int parentIndex = rightIndex >> 1;
            parentMap.get(parentIndex).right = rightNode;
            parentMap.put(rightIndex, rightNode);
        }
        curr++;
    }
    return root;
}

这篇关于算法练习(15)-设计1个二叉树的序列化与反序列化实现?的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！