刷题
刷题
learn
learn
日期
Sep 5, 2024
- 二叉树的层序遍历
- 准备一个队列，把头节点放进去；
- 每次弹出一个节点，如果有左节点就把左节点放进去，有右节点就把右节点放进去（先左后右），什么都没有就只弹出
- 终止条件：队列空
- 改进版1（普通BFS）：
- 改进版2：自己写数组模拟vector
- 二叉树的锯齿形层序遍历
- 思路：加入一个
reverse变量用来判断当前读取的时候是否需要倒着读
- 二叉树的最大特殊宽度
- 把整棵树想象成类似堆那样，每个节点下标和左右孩子是如何对应的
- 然后多加一个下标数组，和节点数组同步增长
- 拿到队列长度
size； - 如下行为重复
size遍： - 弹出
- 有左加左
- 有右加右
- 求二叉树的最大深度、求二叉树的最小深度
- 求最大深度：采用递归的方法，终止条件就是空指针高度为0，否则递归求左右子树的最大高度然后加1
- 注意：最好用
algorithm库中的max函数，否则判断很容易超时！ - 核心问题是：只有到叶节点才算高度，也就是base case有两个：第一个是空树，返回0；第二个是叶节点，左右子树都是空树，返回1；
- 二叉树先序序列化和反序列化、二叉树按层序列化和饭序列化
序列化指的是将原本的一棵二叉树，转换成字符串的方式，这样就可以方便存入硬盘中；
反序列化指的是由硬盘中读取这个字符串，然后将其转换为一棵树的过程
- 利用先序与中序遍历序列构造二叉树
- 可以用一张
HashMap保存每个值在数组中的位置，这样每次就不用遍历了； - 先序遍历的第一个元素，在中序遍历中找到它，然后它左边的就是它的左子树，右边的就是它的右子树
- 验证完全二叉树
- 思路：BFS
- 有右无左：返回
fasle； - 一旦发现孩子不全的节点，接下来必须全是叶节点；
- 求完全二叉树的节点个数，要求时间复杂度低于
- 时间复杂度分析：因为每次并没有直接遍历，而是先判断之后，选择一遍往下递归，所以实际上是级别，也就是级别的复杂度
注意：中序遍历无法完成二叉树的序列化和反序列化，后序遍历可以