目录

1. 数据结构 校招复习(持续更新~)

链表

常见面试题

如何判断链表有环?

双指针?

队列

常见面试题

当循环队列满队退了一个队后,如何获取该队列的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的左叶子

    得出左子树的形状:
    https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E5%B7%A6%E5%AD%90%E6%A0%91%E7%9A%84%E5%BD%A2%E7%8A%B6.jpg
    左子树的形状
  5. 接着分析右子树,把右子树的元素(HMZ)在先序遍历和中序遍历中的顺序拿出来进行比较。

    先序:MHZ(根左右) 中序:HMZ(左根右)

    通过先序特点我们可以确定M是右子树的根结点,根据中序特点确定H是左叶子,Z是右叶子

    得出右子树的形状:
    https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E5%8F%B3%E5%AD%90%E6%A0%91%E7%9A%84%E5%BD%A2%E7%8A%B6.jpg
    右子树的形状
  6. 得出整棵树的形状
    https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E6%95%B4%E6%A3%B5%E6%A0%91%E7%9A%84%E5%BD%A2%E7%8A%B6.jpg
    整棵树的形状
例二

先序遍历: 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

https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E4%BE%8B%E4%BA%8C%E6%95%B4%E6%A3%B5%E6%A0%91%E7%9A%84%E5%BD%A2%E7%8A%B6.png
例二整棵树的形状

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

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

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

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

红黑树

二叉查找树

完美平衡二叉树

红黑树

特性

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

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

常见面试题