Week20 0731--0806

question 1 列表查重

给定一个列表，假如里面有任何重复元素返回true,否则返回false

答案：

利用set函数能很简单的解决这类重复的问题。

下面我用了字典来统计，但是发现用get函数会慢很多

快 55ms
慢 80ms

用了dict的内置函数确实会增加一些时间损耗，所以自己权衡（但是用get方法建立元素统计的话代码很简便）

question 2：查询二叉树里面的两个元素和是不是 k

给定一个查询树，和值k，问树里面的两个元素能不能组成k(和为k）

我的答案：

最开始我想到的是利用二叉搜索树的结构特点，用搜索树来搜索  y=k-cur.val，可以看到这个想法还是比较耗时间的，因为对于每一个节点，都要调用一下搜索

别人的方法：

只遍历一次树，但是将值保存下来，这样每一遇到要查询的时候就调用hash查询，这样能够保证只用O(n)的时间就完成任务。

这里面要明白：假设 树有两个元素 a+b=k，遍历的时候先遇到了a,这时候在hash表中查询b=k-a，没有查询到，保存a到hash表,继续遍历，遇到b，查询hash表a=k-b，成功。所以这种方法只要树里面存在满足要求的元素，一定能查询的到

question 3 建立二叉树

给定一组列表，要求建立二叉树，根节点为列表中最大的元素，左子树由列表左边建立（以最大元素为界），右子树由列表右边建立

我的方法：

这个题目很适合用递归的方法做：

1.找到列表的最大数，将列表分成两部分

2.用最大数建立根节点，递归用子列表建立子节点