Week21 0807--0813

question 1打印二叉树

给定一个二叉树，按要求打印节点

我的方法：

先用BFS遍历整个树得到按层存储的节点，然后对于矩阵的元素位置，找规律。这个方法的问题是BFS没有存储节点位置信息，比如example的level4的节点4，在存储中其位置有可能是同一level的各个地方，所以这个方法无法accept

别人的方法：

递归方法：

1.先计算树的深度，用来建立depth*(2**depth-1)的矩阵

2.建立一个函数fill(root,depth,leftpointer,rightpointer),其中leftpointer,rightpointer用来指引这个节点的元素放的位置（mid=leftpointer+rightpointer/2）

3.对子节点递归这个函数

question 2 找出重复的子树 

题目要求给定一个数，找出这个树中所有重复的子树，并返回重复子树的根

别人的答案：

这道题不会，看别人的讨论

（1）利用 o(n^2）的方法                                                         172ms/ 22%

其实查重的思路还是很简单的，只要树有相同的结构就是重复了。

问题是：怎么确定子树有相同的结构

上面的方法将二叉树转换成元组的结构，每个元组装了 以某节点为根节点的的子树结构（理解递归函数），因为元组(元组可hash是因为元组一旦初始化就不可更改)是可以计算hash值的,也就是说相同结构的子树会算出相同的hash值

然后就和用字典统计字符频率一样了。

关键思想：利用元组的可hash的性质来查重

时间复杂度：

因为对于树内的每一个节点，都要遍历这个节点一下的所有子节点，所以时间复杂度大概是 O(n^2)

(2)改进 O(n)                                               120ms/59%

改进方法涉及到python原生数据结构的问题，也就是tuple元组是不缓存自己的hash值的，所以在计算

tup=root.val,convert2tup(root.left),convert2tup(root.right)

的时候，因为后面两个也是元组，就要不停的递归去算其hash值，这样就导致了O(n^2)的时间复杂度

所以将元组改成能够缓存自身hash值的数据结构（集合set），就可以加快运算时间。问题是集合set本身是可变的，不能hash。但是有一种特殊的set结构叫做frozenset，它是一种特殊的集合，一旦初始化完成后就不可以更改，所以是可hash的，也就是说可以作为字典的key

这里用[]将元组打包也很有讲究，就好像下面的程序一下。因为不希望set对我里面的内容进行去重复，我只是想要hash值，在元组外面再包一个list就能够避免set直接接触到元组，避免对元组进行去重

(3)改进o(n)                                               92ms/97%

第二种方法实际上并不是O(n)的时间复杂度，但是不懂为什么当重复子树很多的时候会出现问题

question 3:两个树是否有重复

我的答案：

由上面题目启发，可以先将其中一个树转换成元组形式,然后再进行查找

关于frozenset与set的区别：

主要区别是frozenset一旦初始化后就不可改变，所以可以用来做字典的key