算法|刷了三个月leetcode算法，顺利拿下百度、阿里等大厂的offer( 二 )

集合
集合是指具有某种特定性质的具体的或抽象的对象汇总成的集体，这些对象称为该集合的元素，其主要特性是元素不可重复。
在Java中， HashSet 体现了这种数据结构，而HashSet是在MashMap的基础上构建的。 LinkedHashSet继承了HashSet ，使用HashCode确定在集合中的位置，使用链表的方式确定位置，所以有顺序。 TreeSet实现了SortedSet 接口，是排好序的集合（在TreeMap 基础之上构建），因此查找操作比普通的Hashset要快（log(N)）；插入操作要慢（log（N））因为要维护有序。
散列表
散列表也叫哈希表，是根据关键键值(Keyvalue)进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数。
Java中HashMap实现了散列表，而Hashtable比它多了一个线程安全性，但是由于使用了全局锁导致其性能较低，所以现在一般用ConcurrentHashMap来实现线程安全的HashMap（类似的，以上的数据结构在最新的java.util.concurrent的包中几乎都有对应的高性能的线程安全的类）。 TreeMap实现SortMap接口，能够把它保存的记录按照键排序。 LinkedHashMap保留了元素插入的顺序。 WeakHashMap是一种改进的HashMap ，它对key实行“弱引用” ，如果一个key不再被外部所引用，那么该key可以被GC回收，而不需要我们手动删除。
树
树（tree）是包含n（n>0）个节点的有穷集合，其中：

每个元素称为节点（node）
有一个特定的节点被称为根节点或树根（root）
除根节点之外的其余数据元素被分为m（m≥0）个互不相交的结合T1 ， T2 ， ……Tm-1 ，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）

树这种数据结构在计算机世界中有广泛的应用，比如操作系统中用到了红黑树，数据库用到了B+树，编译器中的语法树，内存管理用到了堆（本质上也是树），信息论中的哈夫曼编码等等等等，在Java中TreeSet和TreeMap用到了树来排序（二分查找提高检索速度），不过一般都需要程序员自己去定义一个树的类，并实现相关性质，而没有现成的API 。
下面用Java来实现各种常见的树。
二叉树
二叉树是一种基础而且重要的数据结构，其每个结点至多只有二棵子树，二叉树有左右子树之分，第i层至多有2(i-1)个结点（i从1开始）；深度为k的二叉树至多有2(k)-1)个结点，对任何一棵二叉树，如果其终端结点数为n0 ，度为2的结点数为n2 ，则n0=n2+1 。
二叉树的性质：

在非空二叉树中，第i层的结点总数不超过2^(i-1) i>=1;
深度为h的二叉树最多有2^h-1个结点(h>=1) ，最少有h个结点;
对于任意一棵二叉树，如果其叶结点数为N0 ，而度数为2的结点总数为N2 ，则N0=N2+1;
具有n个结点的完全二叉树的深度为log2(n+1);
有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则如果I>1 ，则其父结点的编号为I/2；如果2I<=N ，则其左儿子（即左子树的根结点）的编号为2I；若2I>N ，则无左儿子；如果2I+1<=N ，则其右儿子的结点编号为2I+1；若2I+1>N ，则无右儿子。
给定N个节点，能构成h(N)种不同的二叉树，其中h(N)为卡特兰数的第N项， h(n)=C(2*n n)/(n+1) 。
设有i个枝点， I为所有枝点的道路长度总和， J为叶的道路长度总和J=I+2i 。

满二叉树、完全二叉树
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点；