二叉树

深度优先： 迭代思路
利用栈辅助
先序遍历:
1.当前栈顶节点左右子节点压栈
2.取出栈顶节点，打印。
重复 1 ~ 2 的过程 直至栈空

后序遍历：
1.当前左右子节点压栈
2.取出栈顶节点，推入收集栈，左右节点压栈。
3.直至栈空，打印收集栈各个节点。
其实是对先序遍历结果的逆序。

中序遍历：
以左节点 | |右节点 分解树
1.以head指针取出左子节点，压栈。
2.弹出栈顶元素，判断是否有右子节点。
若有 head = 右子节点 执行 1 操作
3 .重复 1 ~ 2 直至栈和head指针皆空

广度优先：
102. 二叉树的层序遍历
思路：
此次采用 哈希表记录 level层级 + 队列 缓存节点，不使用东哥双循环遍历。
1.mapLevel 记录节点层级，head指针指向节点，level记录当前层级，result缓存返回结果。
2.当head为空时，从队列中取出节点赋值head。
3.当head不为空时，从mapLevel中查询head的层级与level做比对
层级一致时：
将head.val 推入 result[level - 1]数组中（level - 1 也是个数组 起到分层作用)。然后将左右子节点推入队列， 并在mapLevel中 设置层级 level + 1；
并将head置为null 这样才能取队列中的节点避免无限循环。
层级不一致时：
在 result[level - 1] 中 设置一个数组
与此同时 level++（意味着进入下一个层级了
662. 二叉树最大宽度 溢出 告辞
这题的坑在于null节点也计入节点
比如说 1 3 算 宽度为2. 1 null null 3 算宽度为 4.
需要对每一个节点打标 左子树 为 x 2 右子树为 x 2 + 1
··················································
二叉树分类：
搜索二叉树： 中序遍历 || 左右都是搜索二叉树，且符合 左 < 父 < 右，成立（和平衡很像
左子树节点比父节点小，右子节点比父节点大。
剑指 Offer II 052. 展平二叉搜索树
两种解法：1.队列缓存节点法 2.原地修改法（推荐）
剑指 Offer II 055. 二叉搜索树迭代器
解法同上题。

完全二叉树：层序遍历
1.每一层都是满的
2.最后一层可能不满，但不满，也是从左至右依次边满，不会出现中间有空缺的。
剑指 Offer II 043. 往完全二叉树添加节点
方法 1 .利用开辟多余空间，缓存节点。（不推荐 双慢

判断条件：
1）每一个节点，只有右孩子，缺没有左孩子。不是完全二叉树。
2）在 1）的基础不上，如果遇到 第一个 左右两孩子不双全，后续节点必须都是叶子结点

满二叉树:
N 节点数, hight 最大深度。
2 ^ hight - 1 === N 是满二叉树

平衡二叉树:
成立条件：
1.左子树平衡
2.右子树平衡
3.左右子树高度差距不能超过1
110. 平衡二叉树
方法 1
后序遍历
方法 2
前序遍历 + 配合计算深度函数（这里用后序计算方便 方法1去掉前序 直接在后序计算时比较，速度较快）

套路：
基于左右子树要信息，树形DP。
左右子树需要的信息做全集。
后序遍历。
·····················
二叉树的公共祖先
二叉树的最近公共祖先
方法1：map表存储 q || p 祖先节点路径 然后 另一个节点去map表中找祖先节点是否有对应的
方法2: 递归 最优
1.head === o1 || o2 || null 返回 head
2.左右子树 返回值 都不为空 返回 head
3.左右子树返回值 有一个非空 返回非空值
··············
二叉树后继节点
后继特性：
1.X有右子树 右子树中最后一个左子节点为后继
2.X无右子树 往上找，X是否在父节点的左子树，是的话则父节点为后继。

面试题 04.06.后继者
方法 1： 中层遍历 使用 arr缓存数据
剑指 Offer II 053.二叉搜索树中的中
方法 2： 中层遍历 使用 preNode 缓存节点 当 preNode 为 p 当前节点即为后继
方法 3：利用二叉搜索树的节点大小性质（推荐
二叉树序列化与反序列化
先序，数组中确认了空节点。
利用 序列化 层序遍历 反序列化：节点队列 + 遍历字符串数组
剑指 Offer 37. 序列化二叉树
剑指 Offer II 048.序列化与反序列化二