上周牛课堂中奖名单以及本周牛课堂公告

题目一

二叉树的按层打印与ZigZag打印

【题目】

给定一棵二叉树的头节点head，分别实现按层打印和ZigZag打印二叉树的函数。

【例子】

如果一颗二叉树头节点值为1；第二层为2，3；第三层为4，5，6，7。

按层打印时，输出格式必须如下：

Level 1 : 1 

Level 2 : 2 3 

Level 3 : 4 5 6 7

ZigZag打印时，输出格式必须如下：

Level 1 from left to right: 1 

Level 2 from right to left: 3 2 

Level 3 from left to right: 4 5 6 7

题目二

判断一棵二叉树是否为搜索二叉树、完全二叉树、平衡二叉树

题目三

调整搜索二叉树中两个错误的节点

【题目】

一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回。已知二叉树中所有节点的值都不一样，给定二叉树的头节点head，返回一个长度为2的二叉树节点类型的数组errs，errs[0]表示一个错误节点，errs[1]表示另一个错误节点。

【进阶】

如果在原问题中得到了这两个错误节点，我们当然可以通过交换两个节点的节点值的方式让整棵二叉树重新成为搜索二叉树。但现在要求你不能这么做，而是在结构上完全交换两个节点的位置，请实现调整的函数。

题目四

认识布隆过滤器

【题目】

不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64B。现在想要实现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计该系统。

【要求】

1．该系统允许有万分之一以下的判断失误率。

2．使用的额外空间不要超过30GB。

题目五

一致性哈希算法的基本原理

【题目】

工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略：

1．无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，记为key。

2．如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。

请分析这种缓存策略可能带来的问题，并提出改进的方案。