之前分享了朋友面试抖音的真题: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,好让重构二叉树的时候可以知道哪些节点是没有左右孩子的。
题目所给的那棵树序列化:
前序遍历是先 根,然后左右。那么重建的时候也是先根后左右:
说白了,其实跟前序遍历的递归过程是一样的。
所以直接上代码去感受下:
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】原创文章,未经允许,谢绝转载!