好友抖音面试真题：297.二叉树的序列化与反序列化

好友抖音面试

前段时间，好朋友Hellovass参加抖音的面试（高级Android开发工程师）。按照字节的惯例，手撸算法是跑不了的。首先在这里祝好朋友在抖音一切顺利，事事顺心。

题目

终于有心思静下心来搞点事情了，第一件事就是先回顾下好友的面试真题：LeetCode第297题——《二叉树的序列化与反序列化》。

这是一道难度为Hard的题目，其实如果熟悉二叉树的BFS和DFS的话，思路应该会是比较水到渠成的。

题目分析

回到这个题目，题意是你怎么把二叉树变成”一串字符串”，然后又怎么通过字符串重组回一颗二叉树。首先要序列化一颗二叉树，首先肯定要遍历树的各个节点吧：有DFS（深度优先遍历）和BFS（广度优先遍历）。这个题我最开始的想法就是BFS，因为递归是比较抽象的（本人水平有限，所以就抽象了），所以我不会第一时间就往递归上面去想。

假设一棵树：

1
2
3

  2
 / \
1   3

BFS的结果是：

2,1,3

由 2,1,3 怎么重建二叉树呢，不难发现，我们先把根节点2拿出去，剩下的1和3就分别是2的左右孩子了。

假设这棵树再大一点：（题目那颗）

BFS的结果是：

1,2,3,4,5

根据上面的思想，先把root节点拿出来，取后面的两个分别作为左右孩子：

1
2
3

  1
 / \
2   3

这里没问题，继续为2找左右孩子，这时候就取到4,5了，变成：

这里显然就不对了。其实题目已经给了tips：

用上面的思想，按照：

1	1,2,3,null,null,4,5

来重建二叉树，就没有问题了。

那么思路就很清晰了，思路清晰也不代表代码好写，这是两码事；写完代码也不见得所有的test case都能pass。

代码实现

先把序列化的写了，比较传统的BFS，碰到左右子树为空的则输出为nil字符串，这里任意能区分的字符即可。

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    if (root == null) {
        return "nil";
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    StringBuilder sb = new StringBuilder();
    while (!queue.isEmpty()) {
        TreeNode poll = queue.remove();
        if (poll == null) {
            sb.append("nil").append(",");
            continue;
        }
        sb.append(poll.val).append(",");
        queue.add(poll.left);
        queue.add(poll.right);
    }
    return sb.substring(0, sb.length() - 1);
}

反序列化的代码，也是要用到一个队列，跟遍历一样，先把root节点放到队列中，然后不断地循环，把需要找左右孩子的节点继续放入到队列中去：（通过代码注释来讲解）

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data == null || data.isBlank()) {
        return null;
    }
    String[] split = data.split(",");
    // 这里不要忘记了判断第一个结果就是空的情况，本人在这里提交了几遍才找出问题
    if ("nil".equals(split[0])) {
        return null;
    }
    // 先把root节点放到queue里面去
    TreeNode root = new TreeNode(Integer.parseInt(split[0]));
	// index就是你要开始找的孩子节点的位置了。
    // 第二、三个节点肯定是root节点的左右孩子；
    // 然后以此类推：四、五 节点一定是二号节点的左右孩子
    int index = 1;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        // 从队列里拿出一个节点，然后找它的左右孩子
        TreeNode node = queue.remove();
        // 左孩子就是当前index的位置
        String v1 = split[index++];
        // 左孩子
        if (!"nil".equals(v1)) {
            node.left = new TreeNode(Integer.parseInt(v1));
            queue.add(node.left);
        }
        // 右孩子
        String v2 = split[index++];
        if (!"nil".equals(v2)) {
            node.right = new TreeNode(Integer.parseInt(v2));
            queue.add(node.right);
        }
    }

    return root;
}

运行结果

写完放到LeetCode上跑一下看看：

击败数并不高，说明还有更好的写法。但是如果你是面试，其实到这里就已经没有问题了。当然学习不全是为了面试，要不然就真的太累了，希望大家都能找到个好公司，节日福利多多的那种。

谢绝转载

【Happyjava】原创文章，未经允许，谢绝转载！