好友抖音面试真题：二叉树的序列化与反序列化(解法二)

Happyjava

发布于 2020-07-17 10:03:12

3370

发布于 2020-07-17 10:03:12

文章被收录于专栏：Happy的分享Happy的分享

前言

之前分享了朋友面试抖音的真题：LeetCode 297. 二叉树的序列化与反序列化，我用的BFS（广度优先遍历）的方法来做的。事实上，朋友在面试的时候也是用BFS来做的。

BFS的解法点击跳转：好友抖音面试真题：297.二叉树的序列化与反序列化

BFS的运行结果其实不算很满意，所以今天我又用DFS（深度优先遍历）来重新做了一遍，两种方法的耗时对比：

可以看出，DFS是要比BFS快不少的，所以分享下DFS的解法。

题目

还是先看看题目：

前序遍历

这里就不赘述了，直接上代码：

private void ser(StringBuilder sb, TreeNode root) {
    if (root == null) {
        sb.append("nil,");
        return;
    }
    sb.append(root.val).append(",");
    ser(sb, root.left);
    ser(sb, root.right);
}

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    ser(sb, root);
    return sb.substring(0, sb.length() - 1);
}
复制代码

这里碰到为空的情况，需要把结果拼接成nil，好让重构二叉树的时候可以知道哪些节点是没有左右孩子的。

反序列化

题目所给的那棵树序列化：

前序遍历是先根，然后左右。那么重建的时候也是先根后左右：

build(1) // root节点
开始考虑root的左孩子：build(2)
开始考虑2的左孩子：build(nil) // 碰到nil就没了。然后考虑2的右孩子，也是nil。到这里这条路径就结束了
root节点的左孩子考虑完之后，要开始考虑root的右孩子了：build(3)
然后再考虑3的左孩子：build(4)； 3的右孩子:build(5)
以此类推。

说白了，其实跟前序遍历的递归过程是一样的。

所以直接上代码去感受下：

private TreeNode des(LinkedList<String> strings) {
    // 依次取出每一个元素
    String poll = strings.poll();
    // 如果没有了或者 为nil，那么返回 null
    if (poll == null || "nil".equals(poll)) {
        return null;
    }
    // 构建当前节点
    TreeNode root = new TreeNode(Integer.parseInt(poll));
    // 构建当前节点的左孩子
    root.left = des(strings);
    // 构建当前节点的右孩子
    root.right = des(strings);
    // 把当前节点返回出去。（返回出去就变成了它上一个节点的左右孩子了/或者本身就是root节点）
    return root;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data == null || data.isEmpty()) {
        return null;
    }
    LinkedList<String> strings = new LinkedList<>(Arrays.asList(data.split(",")));
    return des(strings);
}
复制代码