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

1,718 阅读2分钟

前言

之前分享了朋友面试抖音的真题: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,好让重构二叉树的时候可以知道哪些节点是没有左右孩子的。

反序列化

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

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

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

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

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

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);
}

总结

递归是一个比较抽象的东西,也很难给讲得透彻。所以对于这种做法,还是需要多琢磨。琢磨透了,下次做题也还是不会,hahaha~~~

谢绝转载

【Happyjava】原创文章,未经允许,谢绝转载!