链表

常见面试题

如何判断链表有环？

• 漫画算法：如何判断链表有环？

双指针？

队列

常见面试题

当循环队列满队退了一个队后，如何获取该队列的index？

% 取模（取余），第几个元素 % 队列长度

树

二叉树

常见面试题

还原二叉树

• 还原二叉树–已知先序中序或者后序中序

做题方法：

1. 找到根结点，确定左子树，确定右子树（最重要）

   如果给出前序遍历，那么前序遍历的第一个元素就是根结点

2. 对左子树进行递归分析

3. 对右子树进行递归分析

已知先序、中序遍历，求后序遍历

例一

先序遍历: GDAFEMHZ 中序遍历: ADEFGHMZ 思路分析：

1. 根据先序遍历的特点——根左右（中左右都可以），第一个元素一定是根结点，所以立即确定G是根结点。
2. 确定了G是根结点后我们就可以去确定左右子树了。根据中序遍历的特点——左根右，可以得知G结点左边的元素ADEF就是左子树，右边的HMZ就是右子树。
3. 接着分别分析左右子树，思路和前面两步一样，把他们当作独立的二叉树来分析。
4. 把左子树的元素（ADEF）在先序遍历和中序遍历中的顺序拿出来进行比较。
   
   先序：DAFE（根左右） 中序：ADEF（左根右）
   
   通过先序特点我们可以确定D是左子树的根结点，根据中序特点确定左边有唯一一个A在D的左边，A就是D的左叶子，右边是EF。
   
   同理，观察EF的相对位置，在先序（根左右）是FE，在中序是EF，得知F是D的右子树根结点（D的右叶子），E是F的左叶子
   
   得出左子树的形状：

   

5. 接着分析右子树，把右子树的元素（HMZ）在先序遍历和中序遍历中的顺序拿出来进行比较。
   
   先序：MHZ（根左右） 中序：HMZ（左根右）
   
   通过先序特点我们可以确定M是右子树的根结点，根据中序特点确定H是左叶子，Z是右叶子
   
   得出右子树的形状：

   

6. 得出整棵树的形状

   

例二

先序遍历: f b a c d e g h 中序遍历: a b d c e f g h 答案：a d c b e h g f a d e c b h g f

已知中序和后序遍历，求前序遍历

中序遍历: ADEFGHMZ 后序遍历: AEFDHZMG 思路分析: （做题方法是一样的）

已知前序、后序遍历，求中序遍历

这种情况可能会无法还原出一个唯一的二叉树，因为无法唯一确定根结点的左右子树

红黑树

• 30张图带你彻底理解红黑树

二叉查找树

完美平衡二叉树

红黑树

特性

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

1. //
2. //
3. //
4. //
5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

常见面试题