树 – 二叉树

完全二叉树：

完全二叉树可以用数组完美匹配位置（先序存储：根左右），

推论一 ： 位置为k的节点，左孩子：2*k + 1 ，右孩子 ： 2 * （k + 1）
推论二： 最后一个非叶子结点的位置： N / 2 - 1 ，n为节点个数

二叉树的遍历

描述： 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

用数组记录二叉树的中序遍历结果，返回数组

何解？

1、递归

2、迭代遍历

很好理解，用stick模拟一个栈，先拿到所有的跟节点左子树中的属于左孩子节点的节点，在慢慢取出来，当外层循环的最后一步指针指向右孩子是，root为空，但栈数组不为空，继续循环，轮空内层循环，拿到倒数第二个左孩子节点，次节点为第一个取出来的节点的中间节点，再到最后拿到这颗小二叉树的右孩子节点，在循环，至此一个小二叉树村晚了，在依次拿上一层的存