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
网友评论