1. 数据结构 校招复习(持续更新~)
目录
链表
常见面试题
如何判断链表有环?
双指针?
队列
常见面试题
当循环队列满队退了一个队后,如何获取该队列的index?
% 取模(取余),第几个元素 % 队列长度
树
二叉树
常见面试题
还原二叉树
做题方法:
找到根结点,确定左子树,确定右子树(最重要)
如果给出前序遍历,那么前序遍历的第一个元素就是根结点
对左子树进行递归分析
对右子树进行递归分析
已知先序、中序遍历,求后序遍历
例一
先序遍历: GDAFEMHZ 中序遍历: ADEFGHMZ 思路分析:
- 根据先序遍历的特点——根左右(中左右都可以),第一个元素一定是根结点,所以立即确定G是根结点。
- 确定了G是根结点后我们就可以去确定左右子树了。根据中序遍历的特点——左根右,可以得知G结点左边的元素ADEF就是左子树,右边的HMZ就是右子树。
- 接着分别分析左右子树,思路和前面两步一样,把他们当作独立的二叉树来分析。
- 把左子树的元素(ADEF)在先序遍历和中序遍历中的顺序拿出来进行比较。
先序:DAFE(根左右) 中序:ADEF(左根右)
通过先序特点我们可以确定D是左子树的根结点,根据中序特点确定左边有唯一一个A在D的左边,A就是D的左叶子,右边是EF。
同理,观察EF的相对位置,在先序(根左右)是FE,在中序是EF,得知F是D的右子树根结点(D的右叶子),E是F的左叶子
得出左子树的形状:左子树的形状 - 接着分析右子树,把右子树的元素(HMZ)在先序遍历和中序遍历中的顺序拿出来进行比较。
先序:MHZ(根左右) 中序:HMZ(左根右)
通过先序特点我们可以确定M是右子树的根结点,根据中序特点确定H是左叶子,Z是右叶子
得出右子树的形状:右子树的形状 - 得出整棵树的形状
整棵树的形状
例二
先序遍历: 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 思路分析: (做题方法是一样的)
已知前序、后序遍历,求中序遍历
这种情况可能会无法还原出一个唯一的二叉树,因为无法唯一确定根结点的左右子树
红黑树
二叉查找树
完美平衡二叉树
红黑树
特性
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质:
- //
- //
- //
- //
- 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。