【010-week2】算法训练营第二周学习总结 #89

第二周学习内容：

第二周习题训练以下3种很重要的数据结构

1. 哈希表  HashMap
2. 二叉树  Binary Tree
3. 二叉搜索树   Binary Search Tree

哈希表  HashMap

1. 定义

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

2. 特性

哈希表  插入和查找的平均时间复杂度为 O(1) 
在做leecode题目的时候，经常使用哈希表保存中间结果，使算法的时间复杂度降低一个数量级,或者在递归中使用哈希表做缓存，减少重复计算，降低算法复杂度。还可以使用哈希表做两个元素的匹配。
常见题目：leecode 1 two sum ， leecode 242 valid-anagram 等

二叉树  Binary Tree

1. 定义

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

2. 特性

二叉树  有三种遍历方式：前序、中序和后序
在做leecode题目的时候，绝大多数二叉树的题目都是用递归来解题的，代码格式十分统一。
同时深度优先遍历DFS和广度优先遍历BFS也常在leecode二叉树题目中使用到。
常见题目：leecode 102 等

二叉搜索树   Binary Search Tree

1. 定义

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；

2. 特性：

二叉搜索树中序遍历的内容是一个从小到大排序的数组。
在做leecode题目的时候，通过这个特性我们可以解决很多关于二叉搜索树的算法题。
常见题目：leecode 98 等