先序、中序、后序的非递归实现

先序

存在以下规则：

1. 弹出栈就输出该弹出的值。

2. 如果有右孩子，如果有左孩子，压入左。

   后序

3. 弹出打印

4. 如果有左节点，压入左，如果有右节点，压入右
5. 使用一个辅助栈收到打印的内容

6. 然后弹出辅助栈，得到的就是后序结果。

   中序（左节点-根节点-右节点）

7. 整条左边界依次入栈

8. 步骤 1 无法继续，弹出节点并打印，然后将节点的右树继续执行步骤 1。

思想：

1. 整棵树是可以被左边界的节点分解掉。

使用一个指针 h 追踪上次打印的节点，当 h 指向左节点，说明父节点需要处理右子树了，如果 h 指向右节点，说明父节点已经处理完毕，
弹出即打印。

按层遍历

1. 队列
2. 通过设置 flag 变量的方式来判断某一层是否应该结束遍历
   1. 使用map：每层节点操作队列时记录所在的层数据（map），然后将节点的左、右子节点入队。判断节点所在的层是否到达下一层，如果是则结算上一层的max，否则当前层的节点数+1。记住，最后一层没有下一层，所以需要对最后层进行结算。
   2. 使用两个指针，curEnd：当前层最右节点，nextEnd，如果有下一层，下一层最右节点。

      二叉树的序列化和反序列化

• 不要忽略空节点，将空节点使用 null 补全。

  返回后继节点

1. 暴力算法：遍历
2. 父子关系

中序遍历：左中右，

当节点是整棵树的右节点时它没有后继节点。
前提是中序遍历。

动态规划：用空间换时间

1. 每一棵树中，左树和右树的高度差不超过 1

2. 列出可能性，这个可能性是根据左、右子树获取的信息的做判断。

   拆分问题

3. 判断是否和头结点有关。