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

发布时间:『 2020-06-26 20:48:21 』  博客类别:未分类  阅读(-1)

好友抖音面试

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

题目

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

这是一道难度为Hard的题目,其实如果熟悉二叉树的BFS和DFS的话,思路应该会是比较水到渠成的。不过面试嘛,状态不一样,比如压力面试,很可能头晕脑胀就反应不过来。记得另外一位朋友面微信的时候就被问了如何找出Binary Search Tree第K大的节点,他当时就没有反应过来,不过后来也顺利拿到微信的Offer了。不过他没去,啊哈哈哈~~~~

题目分析

回到这个题目,题意是你怎么把二叉树变成”一串字符串”,然后又怎么通过字符串重组回一颗二叉树。首先要序列化一颗二叉树,首先肯定要遍历树的各个节点吧:有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】原创文章,未经允许,谢绝转载!


上一篇:没有了~

下一篇:[重学C/C++]WSL+Clion打造C++开发环境


Happyjava的博客

何以解忧?唯有定投!可以是定期投资,也可以是定期学习,不冲突!

个人QQ号: 「1015030682」

联系邮箱: 「happyjava@foxmail.com」

备案号:浙ICP备17032647号-3