二叉树的理论基础
二叉树的种类
满二叉树：如果一棵树只有度(表示节点拥有的子节点数)为0的结点和度为2的节点，并且度为0的节点在同一层上
完全二叉树：在完全二叉树中，除了底层节点可能没有填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若底层为第h层（h从1开始），则该层包含1~2^（h-1）个节点。
二叉搜索树：它是一个有序数。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。left.val < root.val
若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值。right.val > root.val
它的左、右子树也分别为二叉排序树
二叉树的存储方式
链式存储使用指针，顺序存储使用数组
用数组存储如何遍历：
若父节点的数组下标是i,那么左孩子是 i*2+1,右孩子是1*2+2
二叉树的遍历方式
深度优先遍历
前中后指的是中间节点的位置
前序遍历（递归法，迭代法）：
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）
广度优先遍历
层序遍历（迭代法）一般使用队列来实现
二叉树的定义
二叉树的定义和链表差不多，相对于链表，二叉树的节点里多了一个指针，其有两个指针，指向左右孩子。
二叉树的递归遍历
递归三要素：
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑
二叉树的前序遍历
递归遍历
迭代遍历
统一迭代
二叉树的后序遍历
递归遍历
前序遍历是中左右，后序遍历是左右中，把后序遍历反转一下，你发现是中右左，因此我们自遍历的时候按照前序遍历的那样，只不过先要将左孩子放入，再放右孩子，最终返回结果的时候直接反转
迭代遍历
统一迭代
二叉树的中序遍历
递归遍历
迭代遍历
统一迭代
