27. 什么是头指针和头结点？
头指针和头结点是两个不同的概念：
- 头指针是一个指针变量，它指向链表的第一个节点；
- 头结点是链表中的一个实际节点，通常是人为增加的，里面一般不存放真正的数据。
增加头结点的主要目的是让链表操作更加统一。比如删除第一个真正的数据节点时，有头结点之后就不需要特殊处理，可以和删除其他节点采用类似的逻辑。
28. 平衡二叉树、二叉搜索树、完全二叉树有什么区别？
这三个概念关注的是不同的问题：
- 二叉搜索树关注的是节点之间的大小关系：左子树比根小，右子树比根大；
- 平衡二叉树关注的是树的高度，要求左右子树的高度差保持在一定范围内，避免树退化；
- 完全二叉树关注的是树的形状：除了最后一层之外，其他层都要填满，最后一层的节点从左到右连续排列。
[!TIP] 可以简单理解：二叉搜索树看大小，平衡二叉树看高度，完全二叉树看形状。
29. 如何根据遍历序列构造二叉树？
比较经典的是根据前序遍历和中序遍历构造二叉树：
- 前序遍历的第一个节点一定是根节点；
- 找到这个根节点以后，再去中序遍历中找到它的位置，那么它左边的部分就是左子树，右边的部分就是右子树；
- 然后对左右子树重复这个过程，就可以递归构造整棵树。
[!TIP] 这里的关键就是：前序确定根，中序确定左右子树的范围。类似地，中序加后序也可以唯一确定二叉树。
30. 朴素字符串匹配和 KMP 有什么区别？
朴素字符串匹配就是从主串的某个位置开始和模式串比较，如果中途匹配失败，就把模式串向后移动一个位置重新开始。它的问题是前面已经比较过的一些字符信息没有被利用，所以最坏情况下时间复杂度是 O(nm)。
KMP 的核心思想是：利用已经匹配成功的部分，提前知道下一次应该从哪里开始比较。它通过构造 next 或者 lps 数组记录模式串的前后缀匹配信息，因此主串指针不需要频繁回退，匹配过程可以达到 O(n+m)。
[!TIP] 理解 KMP 最重要的不是死记
next数组，而是理解：匹配失败后，不需要把之前的信息全部丢掉。
31. 什么是哈夫曼编码？
哈夫曼编码是一种用于数据压缩的编码方式。
它的基本思想是：出现频率高的字符使用较短的编码，出现频率低的字符使用较长的编码，这样可以减少整体编码长度。
构造的时候，每次选择频率最低的两个节点合并，最终形成一棵哈夫曼树，再根据从根节点到叶子节点的路径生成编码。
比如某些字符出现得特别频繁，就给它比较短的二进制编码；很少出现的字符可以使用更长的编码。
32. 什么是 Trie 树？有什么应用？
Trie 树，也叫字典树，是一种专门用来处理字符串和前缀关系的树。
它不是把一个完整字符串作为一个节点，而是按照字符逐层存储。例如存储 "cat" 和 "car"，它们前面的 "ca" 部分可以共享，因此 Trie 特别适合做前缀查询。
比如搜索框输入 "app"，系统需要快速找到所有以 "app" 开头的单词，就可以使用 Trie 树。
常见应用包括：
- 输入法联想；
- 搜索框提示；
- 字符串前缀匹配；
- 字典查询。
33. AVL 树有哪些旋转情况？
AVL 树要求每个节点左右子树高度差不能超过 1。如果插入或者删除后出现失衡，就需要通过旋转恢复平衡。主要有四种情况：
- LL：在左子树的左边插入，需要右旋；
- RR：在右子树的右边插入，需要左旋；
- LR：先左旋，再右旋；
- RL：先右旋，再左旋。
[!TIP] 其实不需要把四种情况死记，可以先理解它的本质：树往哪边"歪"，就通过旋转把它重新拉回来。
留言板