作为一名程序猿，想在面试的时候游刃有余，首先要熟练掌握数组、字符串、链表、树、栈、队列这几种基础的数据结构。
1 树
树的结构：除根节点外每个节点只有一个父节点，根节点没有父节点；除叶节点外每个节点只有一个或多个子节点，叶节点没有子节点。父节点和子节点用指针链接。
树的遍历：前序遍历、中序遍历、后序遍历，其递归和循环实现都要熟练掌握。此外还有广度优先遍历。
二叉树的特例：
- 二叉搜索树：平均
O(logn)找到一个节点； - 堆：最大堆、最小堆，用于解决快速找到最大最小值的问题；
- 红黑树：规则保证从根节点到叶节点最长路径的长度不超过最短路径的两倍。
1.1 二叉树遍历
前序遍历最先出现的是根节点，中序遍历可以通过根节点划分左右子树，后续遍历最后出现的是根节点。
因此根据中序序列和前序序列（后序序列），可以唯一重建一棵二叉树。但通过前序序列和后序序列无法确定一棵二叉树。
以前序 + 中序为例，方法如下：
-
确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
-
求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
-
递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位
中序遍历时，下一个节点的确定过程：
-
若该节点有右子树，则下一个节点为右子树的左叶子节点；
-
若无右子树，则（1）如果该节点是父节点的左子节点，那么下一个节点为父节点 （2）如果该节点是父节点的右子节点，那么回溯直到找到满足条件（1）的节点。
1.2 二叉树的深度（0622更新）
递归后序遍历，左右子树中较大深度 +1。
1.3 二叉树的路径（0622更新）
前序遍历，借助堆栈思想存储路径。
1.4 最大堆/最小堆（0624更新）
下面以最大堆为例，最小堆类似。
-
是完全二叉树，不一定是满二叉树；
-
父节点大于或等于子节点的值。
由于是完全二叉树，因此借助数组的形式来存储，若数组下标从 1 开始，最大堆中父节点下标与子节点下标是两倍关系。
heap[father * 2] == heap[leftChild];
heap[father * 2] == heap[rightChild];
最大堆的效率：O(1) 完成最大值查找，O(logn) 完成插入和删除。
1.5 红黑树（0625更新）
C++ 中的 set 和 multiset 都是基于红黑树实现的。
红黑树是一种特殊的二叉查找树，它的特征如下：
-
每个节点或者是黑色，或者是红色。
-
根节点是黑色。
-
每个叶子节点都是黑色。这里的叶子节点指为空（nullptr）的节点。
-
如果一个节点是红色的，那么他的子节点必须是黑色的。
-
从一个节点到所有子孙节点的路径上包含相同数目的黑节点。
注意，最后一个特性确保没有一个路径会比其他路径长出两倍，因而红黑树是接近平衡的二叉树。
