数据结构(Java)——Day16(二叉树的OJ题目练习3，堆的基本概念初识)_acm模式和核心代码模式java

一、二叉树的OJ题目练习3

1. 关于牛客和leetcode的ACM模式和核心代码模式

(1)ACM模式：相当于给了一张白纸。需要自己定义类名称，方法名称，输入输出，导包...。即：除了核心代码之外，其他的代码也需要自己实现。一般ACM模式类就叫Main这个类，核心的实现写在主方法main中，需要按照题目要求进行输入输出的管理。

(2)核心代码模式：只需要写核心方法的代码实现即可

2. 二叉树先序遍历(这个先序遍历是包含了空结点)建树，之后中序遍历，输出中序遍历结果：

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

(1)思路

A. 当先序遍历中包含了空节点，则这个先序遍历序列可以唯一的确定一棵树。

若不包含空结点，则只能由先序 + 中序；后续 + 中序才能唯一的确定一棵树

B. 代码思路：

a. 不断的遍历这个前序遍历字符串，每次从中取出一个字符构建树的结点

b. 前序遍历构建

TreeNode root = new TreNode(val);

root.left = 继续上述a流程构建，并返回建立的树的根节点root；

root.right = 继续上述a流程构建，并返回建立的树的根节点root；

c. 终止条件：当碰到root == null的时候，则说明不用建树，直接返回null表示空树即可

C. ACM模式下的输入输出管理：

a. 可能由多组输入数据，因此需要循环读取，每个测试数据占一行

b. 每个结点输出之后加空格，每棵树的输出在同一行

(2)代码实现：

3. 从前序与中序遍历序列(这个前序和中序没有保存空结点)构造二叉树：105. 从前序与中序遍历序列构造二叉树 - 力扣（Leetcode）

(1)思路：

a. 前序遍历结果可以看作是树根的集合，通过index来遍历

b. 建立一个树根结点root

从中序遍历结果中找到等于preorder[index]的索引位置pos

则root.left == build(left,pos - 1);//递归的通过前序遍历和中序遍历区间构建左子树

则root.right == build(pos + 1, rught);//递归的通过前序遍历和中序遍历区间构建右子树

(2)代码实现：

 4. 从后序与中序遍历序列(这个前序和中序没有保存空结点)构造二叉树：

(1)思路：最简单的方法：

A. 将postorder序列反转，得到一个根右左的递归序列

B. 递归构造的时候先构造右子树，再构造左子树即可

(2)实现代码：

二、优先级队列

1. 优先级队列和普通队列(FIFO结构)比较：

(1)入队一样，默认从队尾入队

(2)出队的时候按照优先级出队，优先级高的先出队，优先级相同的则按照先进先出（FIFO

2. 优先级队列(是逻辑结构，具体的实现是通过物理结构——堆)的特点：

(1)元素个数动态变化

(2)按照优先级出队，优先级高的优先出队，相同则FIFO

3.  优先级队列能否使用排序数组来替代

(1)对于优先级队列来说：能够做到添加删除元素的时间复杂度比较低

(2)对于排序数组来说：数组排序之后，元素是固定的。如果要添加新元素又需要重新排序，时间代价太大 

三、优先级队列的实现——堆

1. 堆的特点：

(1)堆是一颗完全二叉树，一般使用动态数组存储具体元素

注: 用动态数组存储完全二叉树，存储密度比较高(不用存储空结点)，查询效率比较高

(2)关于元素的值分为两类堆：

最大堆/大根堆：任意一个结点的值> = 其子树节点的值

最小堆/小根堆：任意一个结点的值< = 其子树节点的值

注意1：JDK的堆的实现是最小堆的实现且不存储相同的值

注意2：基于上述的特点，最大堆的堆顶元素一定是最大值；最小堆的堆顶元素一定是最小值