首先二叉树的遍历分为，深度优先遍历（dfs）、广度优先遍历（bfs）。

注意：但凡遍历都要注意根节点为 null；

深度优先遍历又分为前中后序遍历，前面文章都讲过了，递归三个语句换个位置就解决了。

注意：这里是深度优先遍历结果放在一个集合里 List 。广度优先遍历（层序遍历）才能分到不同的 List 中， {{1，3}，{4，1}}的形式。

但凡是遍历，不论是深度（栈）、广度（队列），都是弹出一个再判断是否要塞（是否存在左右孩子）。

深度优先的迭代做法后序遍历就是把前序的 left 、 right 压入顺序反转一下，再把得到的 List 反转一下，为什么？因为中前后（前序）、前后中（后序），后序逆转就是中后前，后前再逆转，就是中前后（前序）。关系明了吧！中序就不同，需要借助一个辅助的 cur 树节点，让其初始指向 root 根节点，利用 cur 和 stack 作为条件判空控制循环，然后 cur 不断变换位置。细节自己抠！前后序是 双if，中序 if…else…

广度优先遍历（层序遍历）：

递归（不推荐）方法利用 deep 控制深度。一个 if 判 root 空，一个 if（size < deep） 控制是否创建一个 List 存该深度的结点，resList.get(deep - 1).add(node.val); 最后两个递归完美收官。这里可以选择放入一个 List，也可以放入 List 中的 List，按需求来。

迭代法（墙裂推荐！）：迭代法可以解决很多的遍历问题，而且很方便！主要就是利用队列，深度用循环来控制，条件为非空，那肯定是要不断有新的结点 offer 进来和 poll，这又要限制遍历一个深度再里面元素的次数了，这是又一个循环，这个循环不断进出，长度一直在变，所以要有个在内循环不变、外循环变化的 len 来控制内循环次数，每一次外循环都记录下该层深度的节点个数。

根据遍历返回树后有感

到这里才发现。自己对遍历的认识是多么浅，别人写遍历的时候是根据遍历写代码，我是根据递归的代码来想遍历。这样也未尝是件坏事，至少把递归的前中后序遍历死死记住了.

为什么前序求高度后序求深度?

因为前序先走到叶子节点再 add，而后序是从头结点一路吃过去。add 我称为吃。

其实理解递归/遍历 这样：

前序：中左右：中是吃的操作，左右都是遍历，这样就能很好的理解遍历为何先进这个而不是那个。

PS：堆是一棵完全二叉树，同时保证父子节点的顺序关系（有序）。 但完全二叉树一定是平衡二叉树，堆的排序是父节点大于子节点，而搜索树是父节点大于左孩子，小于右孩子，所以堆不是平衡二叉搜索树 。 持续更新中…… 如有错误，敬请斧正…..