数据结构

基本数据结构有数组（连续）和链表（非连续）两种。其他数据结构如栈、队列、堆、图等都属于基于两者的不同具体。

• 数组：连续的内存空间，可以随机访问，但必须在初始化时确定大小。数组扩容需要重新分配一块内存空间，然后把内容全部复制过去，时间复杂度 O(n)。随机元素的删除（插入）同样也是需要将后面的元素前移一位，时间复杂度 O(n)。

• 优点：可以随机访问；节省存储空间（不需要额外的索引）

• 链表：不连续的内存空间，每个元素保存指向前（后）元素的指针，会造成额外的空间开销。不支持随机访问，只能通过指针（索引）访问元素。但是插入和删除的时间复杂度是 O(1)。

• 优点：不存在扩容问题，插入和删除的时间复杂度是 O(1)。

二叉树

遍历 Binary Tree Traversal

分为递归式和迭代式，递归式简单，迭代式可以用Stack实现。

遍历的前后顺序是相对于根节点而言的，即根节点在最前为前序遍历，根节点在最后为后序遍历。

前序遍历 preorder

中 -> 左 -> 右

中序遍历 inorder

左 -> 中 -> 右

后序遍历 postorder

左 -> 右 -> 中