好友抖音面试
前段时间，好朋友Hellovass参加抖音的面试（高级Android开发工程师）。按照字节的惯例，手撸算法是跑不了的。首先在这里祝好朋友在抖音一切顺利，事事顺心。
题目
终于有心思静下心来搞点事情了，第一件事就是先回顾下好友的面试真题：LeetCode第297题——《二叉树的序列化与反序列化》。
这是一道难度为Hard的题目，其实如果熟悉二叉树的BFS和DFS的话，思路应该会是比较水到渠成的。
题目分析
回到这个题目，题意是你怎么把二叉树变成"一串字符串"，然后又怎么通过字符串重组回一颗二叉树。首先要序列化一颗二叉树，首先肯定要遍历树的各个节点吧：有DFS（深度优先遍历）和BFS（广度优先遍历）。这个题我最开始的想法就是BFS，因为递归是比较抽象的（本人水平有限，所以就抽象了），所以我不会第一时间就往递归上面去想。
假设一棵树：
2
/ \
1 3
BFS的结果是：
2,1,3
由 2,1,3 怎么重建二叉树呢，不难发现，我们先把根节点2拿出去，剩下的1和3就分别是2的左右孩子了。
假设这棵树再大一点：（题目那颗）
1
/ \
2 3
/ \
4 5
BFS的结果是：
1,2,3,4,5
根据上面的思想，先把root节点拿出来，取后面的两个分别作为左右孩子：
1
/ \
2 3
这里没问题，继续为2找左右孩子，这时候就取到4,5了，变成：
1
/ \
2 3
/ \
4 5
这里显然就不对了。其实题目已经给了tips：
用上面的思想，按照：
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】原创文章，未经允许，谢绝转载！
