444，二叉树的序列化与反序列化 - 数据结构和算法的个人空间 - OSCHINA

安宇雨 - 随手采集
2020-08-28 15:42:31
随手采集
0000-未整理-等待研究

It's easy to find if you know what you're looking for.

如果你知道自己想追求什么，就很容易成功。

问题描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"

BFS解决

这题上面说了一大堆，其实就是把二叉树转化为一个字符串，并且还能把这个字符串还原成原来的二叉树就可以了。

把二叉树转化为字符串可以有很多种方式，比如前序遍历，中序遍历，后续遍历，BFS，DFS都是可以的，对于树的各种遍历具体可以看下373，数据结构-6,树。但这题还要求把字符串再还原成原来的二叉树。最容易想到的就是BFS，就是一层一层从往下遍历

来看下代码

 1public class Codec { 2 3    //把树转化为字符串（使用BFS遍历） 4    public String serialize(TreeNode root) { 5        //边界判断，如果为空就返回一个字符串"#" 6        if (root == null) 7            return "#"; 8        //创建一个队列 9        Queue<TreeNode> queue = new LinkedList<>();10        StringBuilder res = new StringBuilder();11        //把根节点加入到队列中12        queue.add(root);13        while (!queue.isEmpty()) {14            //节点出队15            TreeNode node = queue.poll();16            //如果节点为空，添加一个字符"#"作为空的节点17            if (node == null) {18                res.append("#,");19                continue;20            }21            //如果节点不为空，把当前节点的值加入到字符串中，22            //注意节点之间都是以逗号","分隔的，在下面把字符23            //串还原二叉树的时候也是以逗号","把字符串进行拆分24            res.append(node.val + ",");25            //左子节点加入到队列中（左子节点有可能为空）26            queue.add(node.left);27            //右子节点加入到队列中（右子节点有可能为空）28            queue.add(node.right);29        }30        return res.toString();31    }3233    //把字符串还原为二叉树34    public TreeNode deserialize(String data) {35        //如果是"#"，就表示一个空的节点36        if (data == "#")37            return null;38        Queue<TreeNode> queue = new LinkedList<>();39        //因为上面每个节点之间是以逗号","分隔的，所以这里40        //也要以逗号","来进行拆分41        String[] values = data.split(",");42        //上面使用的是BFS，所以第一个值就是根节点的值，这里创建根节点43        TreeNode root = new TreeNode(Integer.parseInt(values[0]));44        queue.add(root);45        for (int i = 1; i < values.length; i++) {46            //队列中节点出栈47            TreeNode parent = queue.poll();48            //因为在BFS中左右子节点是成对出现的，所以这里挨着的两个值一个是49            //左子节点的值一个是右子节点的值，当前值如果是"#"就表示这个子节点50            //是空的，如果不是"#"就表示不是空的51            if (!"#".equals(values[i])) {52                TreeNode left = new TreeNode(Integer.parseInt(values[i]));53                parent.left = left;54                queue.add(left);55            }56            //上面如果不为空就是左子节点的值，这里是右子节点的值，注意这里有个i++，57            if (!"#".equals(values[++i])) {58                TreeNode right = new TreeNode(Integer.parseInt(values[i]));59                parent.right = right;60                queue.add(right);61            }62        }63        return root;64    }65}

DFS解决

DFS遍历是从根节点开始，一直往左子节点走，当到达叶子节点的时候会返回到父节点，然后从从父节点的右子节点继续遍历……

 1class Codec { 2 3    //把树转化为字符串（使用DFS遍历，也是前序遍历，顺序是：根节点→左子树→右子树） 4    public String serialize(TreeNode root) { 5        //边界判断，如果为空就返回一个字符串"#" 6        if (root == null) 7            return "#"; 8        return root.val + "," + serialize(root.left) + "," + serialize(root.right); 9    }1011    //把字符串还原为二叉树12    public TreeNode deserialize(String data) {13        //把字符串data以逗号","拆分，拆分之后存储到队列中14        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));15        return helper(queue);16    }1718    private TreeNode helper(Queue<String> queue) {19        //出队20        String sVal = queue.poll();21        //如果是"#"表示空节点22        if ("#".equals(sVal))23            return null;24        //否则创建当前节点25        TreeNode root = new TreeNode(Integer.valueOf(sVal));26        //分别创建左子树和右子树27        root.left = helper(queue);28        root.right = helper(queue);29        return root;30    }31}

总结

把二叉树转化为字符串很简单，关键是怎么把转化的字符串再还原成原来的二叉树，这里使用BFS和DFS都很容易实现。