栈/队列

栈和队列一般会是你用来解题的数据结构的一部分。你应该知道如何用链表和数组两种方式来实现它们。 加练两道题：[利用两个队列实现一个栈](http://stackoverflow.com/questions/688276/implement-stack-using-two-queues)，以及[利用两个栈来实现一个队列](http://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks)。 ### 树/二叉树/二叉搜索树（BST）/字典树/堆 你可能不会每天都见到树和图，但你很可能会在面试时遇到它们，所以你要彻底地看一下这些数据结构。 树最一般的定义，是和其他结点没有或者有一个以上关系的结点的集合，但在实践中，当面试官说“**树**”的时候，他们指的是一种叫二叉树的东西。**二叉树**是一种树的类型，它的每个结点都至多有两个子树，一般被称为左子树和右子树。 你不应该把**二叉树**和**二叉搜索树**混淆起来，后者是一种特殊的二叉树，它的左子树结点上的值都比父结点小，而右子树结点上的值都比父结点大或者相等。二叉搜索树的优点是，如果树的结构相对平衡（向面试官问清楚这个问题），那么查找、插入和删除就可以在O(log n)的时间里完成。二叉搜索树的其他重要属性，就是你跟着所有的左子树走，就能得到这个树上最小的元素，而跟着所有的右子树走，就能得到这个树上最大的元素。 请注意，是有办法让树一直保持平衡的，最常用的办法就是红黑树和AVL树。我不会去弄清楚它具体实现的细节，只要知道有这些数据结构就行。 不过你绝对必须知道遍历树（[**tree traversal**](http://en.wikipedia.org/wiki/Tree_traversal)）算法：广度优先搜索（[**breadth-first-search**](http://en.wikipedia.org/wiki/Breadth-first_search%22%20%5Cl%20%22Pseudocode)）、深度优先搜索（[**depth-first-search**](http://www.jianshu.com/%22http)），以及**中序遍历**、**后序遍历**和**前序遍历**之间的差别。 以下是在Java实现中序遍历的例子，它可以打印出一个树的所有值（前序遍历和后序遍历几乎和这个一样）： ~~~ void inOrderTraversal(Node root) { if (root == null) return; inOrderTraversal(root.getLeft()); // Do something with the value System.out.println(root.getValue()); inOrderTraversal(root.getRight()); } ~~~ 字典树（[**trie**](http://en.wikipedia.org/wiki/Trie)**，读****“tree”**）常常被用在字符串问题里，它是一个n元树，除了根结点以外的每个结点都代表一个字符或者部分或完整的单词，而且沿着树的每一条路径都代表一个单词。实际上它真的没有听起来那么复杂，只要读一下维基百科上的页面、了解该如何构建一个字典树以及如何查询其中的数值就行。请注意，你可以通过前序遍历输出字典树中的所有键。作为一个练习，你可以想一想自己会如何利用字典树实现自动完成功能。 最后是堆（[**heaps**](http://en.wikipedia.org/wiki/Heap_)），它也被称为优先队列，是你应该了解的最后一种数据结构。它们通常都是满足**堆属性**的二叉树：每个结点的子树的值都比结点本身的值小，或者与它相等。所以根结点的值总是最大的，也就是说你总能找到最大值，但代价就是寻找其他任何一个值所需的时间都是O(n)。插入和删除所需的时间依然是O(log*n)*。