二叉树
解题过程中可能会遇到的二叉树类型可以分为：满二叉树和完全二叉树。
满二叉树：如果一个二叉树只有度为0和2的结点，且所有度为0的结点都在二叉树的同一层，则称这个二叉树为满二叉树。满二叉树形如：
完全二叉树：完全二叉树中只有在最底层可能没有被结点填满，其余每层的结点数都达到了最大值。并且最下面一层的结点都集中在该层最左边的若干位置。而最底层(设为第k层)可能包含的结点数为1~2^(k-1)。完全二叉树形如：
二叉搜索树：二叉搜索树中的每个结点都是有数值的，所以二叉搜索树是一个有序树。
二叉搜索树的特点：根节点的左子树上结点的值均小于根节点的值；根节点的右子树上结点的值均大于根节点的值；且这个原则在二叉搜索树的左右子树上仍然递归成立。二叉搜索树形如：
平衡二叉搜索树(AVL)：它是一个空树或其左右两个子树的高度差的绝对值小于等于1，且其左右子树也递归满足这一要求。平衡二叉搜索树形如：
在上图图三中，这棵树不是平衡二叉搜索树，因为根节点的左子树的高度为2，而根节点的右子树的高度为0，左右子树的高度差为2，大于1，所以不是平衡二叉搜索树。
二叉树的存储方式：既可以通过链式存储(即指针)实现，也可以通过顺序存储(即数组)实现。使用链式存储实现二叉树时，每个结点除了记录该结点保存的数值之外，还需要通过两个指针，分别指向其左孩子结点和右孩子结点。使用顺序存储实现二叉树时，若父节点在数组中的下标为i，则其左孩子结点在数组中的下标为2*i+1，其右孩子节点在数组中的下标为2*i+2。而链式存储二叉树是更常见的方法。
二叉树的遍历方式：二叉树的遍历方式包括：深度优先遍历和广度优先遍历两种。而前序中序后序遍历属于深度优先遍历，层序遍历属于广度优先遍历。前序中序后序遍历的区别在于，遍历时根结点相对于其左右孩子节点的位置不同。根左右为前序遍历，左根右为中序遍历，左右根为后序遍历。深度优先遍历的方式为先往深走，遇到叶子结点再往回走；而广度优先遍历的方式为一层一层的去遍历。
注意：由于深度优先遍历是通过递归的方式实现的，而栈就是实现递归的一种数据结构，所以深度优先遍历可以通过栈来实现；而广度优先遍历一般是使用队列这种数据结构实现的，利用了队列先进先出的特性来一层一层的遍历二叉树。
二叉树的定义：链式存储中二叉树结点的定义方式如下所示：
可以看出，二叉树中每个结点和链表中的每个结点非常类似，每个结点中不仅包含该结点记录的数据值，还包含两个指针，分别用于指向该结点的左孩子结点和右孩子结点。
二叉树的递归遍历：
在写递归算法时需要注意的三要素：
①确定递归参数和返回值；确定哪些参数是递归的过程中需要处理的，那么就在递归函数的方法参数位置加入该参数。
②确定终止条件；若在递归函数中出现了栈溢出的错误，则肯定是终止条件没有写对。
③确定单层递归的逻辑。
二叉树的前序遍历为：
二叉树的中序遍历为：
二叉树的后序遍历为：
144.二叉树的前序遍历：这道题在上述讲解中已经讲过，实现起来非常简单。需要注意前中后序遍历的顺序，根节点处理顺序的不同造成了这三种遍历的区别。注意每次递归调用遍历方法时递归结束是如何处理的。这道题的递归和非递归做法都已自己做出并提交到了leetcode上。注意，如果使用栈，则需要先处理右孩子结点再处理左孩子结点。
145.二叉树的后序遍历：和144题非常类似。需要注意的是，通过递归方式实现二叉树的遍历是很耗费空间复杂度的。
94.二叉树的中序遍历：和上述两题非常类似，简单题。
