数据结构与算法（二叉树）~ 介绍二叉树以及力扣上几道二叉树题目的方法和套路
☺ 需要明白的点是：在方法 执行的 遍历过程中 ❀ 根（或父节点）：是一个结点， ✿ 左子树（是一个区间，左区间，只是当它只有一个结点时才变成一个左结点） ✿ 右子树（也是一个区间，右区间，只是当它只有一个结点时才变成一个右结点） |
1，二叉树的数据结构：
（1）基本实现（组成）：由一个一个根（或父结点）和左结点、右结点构成。
自己动手实现：定义了一个含有 数据域 和 左结点指针、右结点指针 + （父结点【自己设计就加上，这样方便后续的一些操作】） 的 结点类Node。
（2）二叉树【需要先定义为一颗什么类型的二叉树（这样才能按照一定规则进行结点位置的添加），这里咱设计一棵 二叉搜索树】主要的功能（增删改查）：定义一些接口方法
■ 主要的功能（增删改查 + 各种方式的遍历 【前序遍历、中序遍历、后序遍历、层序遍历】+ 前驱结点、后驱结点（针对中序遍历的）+ 树的深度 + 是否为完全二叉树 ）：
● 增加：制定一定比较规则（具体实现：【 二叉搜索树中传入一个比较器类对象（属性对象，可以不写，java内置有一个compator 比较器接口 ~ 组合关系）】 /
【让二叉搜索树 继承 比较类（java内置了comparable 接口） ~ 继承关系/ 将对象进行强制类型转化，然后就可以使用相应的接口方法啦，例如以下：~强制类型转化】）
● 删除：先查找到给结点，然后删除结点：删除过程~~~~~
● 查找：查找结点。
● 前序遍历： 根（父） 左子树 右子树 | 根（父） 右子树 左子树 【前序只需满足 根最先访问】
● 中序遍历： 左子树 根（父） 右子树 | 右子树 根（父） 左子树 【中序只需满足 根中间访问】
● 后序遍历： 左子树 右子树 根（父） | 右子树 左子树 根（父） 【后序只需满足 根最后访问】
● 层序遍历： 一层一层的结点从左到右进行访问。
● 前驱结点：中序遍历的前一个结点。
● 后驱结点：后序遍历的后一个结点。
（3）过程中进行重构二叉搜索树，将 增删改查 或者一些通用的接口或者属性封装到外部抽象类或者接口（方便设计给其他类用这样子）：
2，二叉树的力扣算法题：
总结一些小套路吧 （没有通用的套路，就讲一下方法哈）：
✿ 自己需要先知道的是二叉树的特点就是左右子树（左右结点）构成（一般没有特别强调的二叉树，结点类就是左右子树（结点）（没给父指针结点哈，咱自己设计加的））
套路： 层序遍历：一层一层从左到右，一个一个结点的遍历。使用的数据结构是 队列。
（1）101_对称二叉树 的方法 和 套路：
方法一：（该过程使用层序遍历~迭代的，使用的数据结构是队列（为何数据结构使用队列：一层一层从左边到右边【父节点A 先于 父结点B， 则父节点A 的孩子 会先于 父结点B 的孩子】）
~两个“镜子”同时进行添加~ 不过作者用一面镜子成双对称式添加方式，变成了两个“镜子” ）
思路是：
● 两块镜子的思维：第一个镜子添加进入了左，则第二个镜子添加进入了右 然后第一个镜子添加进入了右，第二个镜子添加进入了左
● 非常非常的巧妙的一个点是作者通过了一个队列的数据，（同时成双添加）结果实现了一个镜子变成两个镜子的效果
● 这里使用的数据结构是：队列（特点先进先出），为了进行（“两面镜子”）每一层的遍历的同步对比
（2）102_二叉树的层序遍历 的方法与套路 ：
方法一：
思路是： 该过程使用层序遍历~迭代的，使用的数据结构是队列（为何数据结构使用队列：一层一层从左边到右边【父节点A 先于 父结点B， 则父节点A 的孩子 会先于 父结点B 的孩子】）
（3）104_二叉树的最大深度 的方法与套路 ：
方法一：该过程使用层序遍历~迭代的，使用的数据结构是队列（为何数据结构使用队列：一层一层从左边到右边【父节点A 先于 父结点B， 则父节点A 的孩子 会先于 父结点B 的孩子】），然后只需要知道当前层遍历完毕（遍历到最后一个结点，这里咱定义一个辅助变量，通过辅助变量数量为 0 时知道进入下一层~ 通过分析，得知：辅助变量= queue.size() ）
（4）105_从前序与中序遍历序列构造二叉树 的方法与套路 ：
方法一：
思路是：
* 前序特点：第一个便是根结点（知道根比较快），中序：左 根 右
* 前序提供的根结点， 中序不断地划分成左子树、右子树
套路：定义一个 map，键值对，中序的【值， 位置】，方便通过（前序提供的根）值确定到位置对应中序中的位置，从而让中序 划分出左子树、右子树。
（5）106_从中序与后序遍历序列构造二叉树 的方法与套路 ：
方法一：
思路是：
* 后序特点：最后一个便是根结点（知道根比较快），中序：左 根 右
* 后序提供的根结点， 中序不断地划分成左子树、右子树
套路：定义一个 map，键值对，中序的【值， 位置】，方便通过（后序提供的根）值确定到位置对应中序中的位置，从而让中序 划分出左子树、右子树。
（6）107_二叉树的层序遍历II 的方法与套路 ：
方法一：从叶子到根的遍历（层序遍历）~ 思路：倒序：只需要不断插入第一个位置
（7）114_二叉树展开为链表 的方法与套路 ：
方法一：
思路是：题目给提示了呀：“展开后的单链表应该与二叉树 先序遍历 顺序相同。”
咱就利用先序遍历的递归或者迭代遍历到每个结点，将其添加到list 集合中，（为什么要添加到List 而不直接操作：）
理由：咱需要重塑一颗树的形状呀（不是你想变就能变）
//然后咱再遍历每个结点，将其左指针指向null，右指针指向下个结点（构建出链式形状）
（8）144_二叉树的前序遍历 的方法与套路 ：
☺ 树的形状：【左区域（左子树） 根（父结点） 右区域（右子树）】 ☺☺☺ 对于树的遍历，到下一层，在形式上是先到了“根”（父结点）上。☺☺☺ ☺前序遍历【根数据先出，然后才是左或者右子树的数据】： 【左区域（左子树）：数据需要先出根数据，然后才是左、右小小子树数据 根（父结点） 右区域（右子树）：数据需要先出根数据，然后才是左、右小小子树数据】 |
方法一：递归实现
方法二：迭代实现：使用的数据结构是栈（为何数据结构使用栈：左区域：一层一层从左不断地往左，（不断地拿到根的结点，将数据添加上）直到没有左了【左为null】，然后从最后这个左【null】这一层层开始，因为没有左了，pop 掉的是当前的根（已经遍历过的结点），然后就开始右结点区域。
| TreeNode node = root; while (!stack.isEmpty() || node != null) { while (node != null) { res.add(node.val); stack.push(node); node = node.left; } node = stack.pop(); node = node.right; } |
（9）145_二叉树的后序遍历 的方法与套路 ：
方法一：递归实现
方法二：迭代实现：使用的数据结构是栈（为何数据结构使用栈：一层一层从左不断地往左，（不断地拿到根的结点）直到没有左了【左为null】，然后从最后这个左【null】这一层层开始，pop出当前根结点，寻找右结点，然后就开始右子树区域：可能右区域（右子树不存在哦）：
① 没有右子树，则已经遍历完数据（左右数据null、null）：这是轮到根数据，添加根数据，然后记录当前结点（可能会是下一次的右区域），然后置空根结点；
② 有右子树：把根结点 push回去，还没轮到添加根的数据（左右区域数据的添加优于根数据），切换到右区域 ；
| TreeNode prev = null; while(!stack.isEmpty() || root != null) { while(root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (root.right == null || root.right == prev) { list.add(root.val); prev = root; root = null; //不加：超出内存 } else { stack.push(root); root = root.right; } } |
（10）226_翻转二叉树 的方法与套路 ：
方法一：递归：（前、后序递归），遍历拿到当前结点时就将其左右子树（结点）进行交换。（中序遍历）：因为先处理好左子树，然后进行交换，处理过的左子树到了右边去了，原先没处理的右子树现在在左边。
方法二：迭代：层序遍历：遍历到当前结点时将左右结点进行交换。
（11）559_N叉树的最大深度 的方法与套路 ：
方法一：递归：细节：遍历每个孩子前 height 必须等于 1;
方法二：迭代 : 使用到了层序遍历的框架【队列】（通过辅助变量知道当前层到了最后一个结点）/ 或者通过 Pair 对象（与map 差不多，只是它可以直接存或取俩个数据（一对））
（12）589_N叉树的前序遍历 的方法与套路 ：
方法一：递归实现：先拿到当前结点，然后遍历孩子树
方法二：迭代实现：利用到了栈的特点跟集合倒序(拿到根结点后，先添加根的数据，然后逆置孩子树结点：Collections.reverse(node.children); 再把孩子树的添加进去栈)
（13）590_N叉树的后序遍历 的方法与套路 ：
方法一：递归实现：先遍历孩子树：然后再拿到当前结点。
方法二：迭代实现：利用到了栈的特点，拿到当前父结点（pop 出来拿到它）~将其 数据倒序添加进当前“所谓的第一个位置” ，然后再实现遍历添加孩子树【倒序添加进当前“所谓的第一个位置”】，这样便实现： 孩子树的数据在根结点之前。
（14）662_二叉树最大宽度 的方法与套路 ：
方法一：直接套用层序遍历的框架（有bug：来自于，无法应对null的中间结点），使用map无法做到，
需要像官网那样封装一个类（标记结点位置的）~ 然后刚刚进入下一层时（通过一个辅助变量进行判断是否进行了下一层~ 当深度辅助变量 ！= 当前结点的深度时，进入下一层 ），标记最左的位置，然后遍历每个位置与之进行取最大宽度，最后返回最大的宽度。
（15）889_根据前序和后序遍历构造二叉树 的方法与套路 ：
方法一：
思路是：
* 前序特点：第一一个便是根结点（知道根比较快），后序： 左 右 根
* 前序提供的根结点， 后序不断地划分成左子树、右子树
套路：定义一个 map，键值对，后序的【值， 位置】，方便通过（后序提供的根）值确定到位置对应后序中的位置，从而让后序 划分出左子树、右子树。
（16）94_二叉树的中序遍历 的方法与套路 ：
方法一：递归实现
方法二：迭代实现：使用的数据结构是栈（为何数据结构使用栈：一层一层从左不断地往左，（不断地拿到根的结点）直到没有左了【左为null】，然后从最后这个左【null】这一层层开始，pop出当前根结点，并将根数据进行添加，然后就开始右子树区域。
| while(node != null || !stack.isEmpty() ) { while(node != null) { stack.push(node); node = node.left; } node = stack.pop(); list2.add(node.val); //已经拿到当前结点了 node = node.right; } |
总结：【前、中、后序的迭代遍历~使用到了栈数据结构】：
1，为啥：一开始就不断地往左，往左：while(node != null){ .... node = node.left; }?
❀ 因为需要到下一层【而下一层就是 左 右】，咱先到达最近的左呗。
【在不断地通过node = node.left, 到达下一层的遍历过程，其实在形式上是到达下一层的根，先到达了下一层的根结点。】
套路哈哈哈：
1，想要使用递归【当直接使用不了题目给的参数是，可以自己定义一个同名（参数自己定，然后不断的递归）】
题意给的方法再调用该方法即可。例如力扣：106_从中序与后序遍历序列构造二叉树：
* public TreeNode buildTree(int[] inorder, int[] postorder) 这个方法是题目本身，这个接口无法直接递归调用实现生成目的。
* public TreeNode buildTree(int is, int ie, int ps, int pe) 这个方法是自定义的
* 使用递归突破点：什么时候跳出return：往往看传入的参数的关系（当参数变化到不合理是即退出）
2，map 哈希表非常有作用哈哈，有一一对应的关系【相当于字典】
