算法题中树相关的题目是相对比较难的，同时在开始刷算法题时，也最好先从树型题刷起，因为他的解题思想对以后各种题型都是有帮助的。在对与树型相关的题目我们多练习发现还是有解题框架我们可以套用的。本篇先简单介绍一下树型数据结构的定义，然后讲解下树形题的大致解体思路。在面对一个数据结构时，我们要看他的存储和遍历，毕竟数据结构就是为了方便我们遍历而存在的。
树定义
表示逻辑上的一对多关系，每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。为什么叫做树呢，因为把显示中的树倒过来就是我们经常看到的树型结构了。常用树定义
- 多叉树：不限制每个结点的子节点数量的树型结构。
- 二叉树：每个结点最多有两个子节点，上面的树型结构就是二叉树。左边的叫左子树，右边的叫右子树。
二叉树的使用很广泛，所以下面的存储和遍历都以二叉树为例。
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
-
完全二叉树：叶子结点只存在在最后一层或倒数第二层。并且如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。
image 平衡树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡树有很多常用的使用方法，比如有红黑树、AVL等。
二叉搜索树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
AVL：加了平衡条件的二叉搜索树，因为平衡后深度更浅，那么搜索的性能更高了。
树的存储
面对上面的结构，我们怎么存储树型结构呢？
在计算机中，存储方式只有两种，一个是数组，一个是链表。数组是存储在连续的内存上，所以我们可以根据偏移量直接找到内存的地址，但是在我们插入和删除元素时，因为要保证连续性，需要把前移或后移保证连续性，效率比较低。链表，相当与一个链条，不需要存储在连续的内存上，只要第一个结点保存下一个的引用即可，这样我们随机访问就不能通过内存的偏移量直接找到地址了，而需要从第一个位置往后遍历，随机访问效率比较低，但是插入和删除的效率比较高，因为我们不用移动元素，只要修改下一个结点的引用既可。树型结构也可以通过数组和链表存储。
数组存储
怎么使用数组存储呢？面对上面的树型结构，直观的想我们可以一层一层的存储，ABCDEFG，但是发现这样会丢失是左子树还是右子树。所以在在缺失左右结点的情况下，我们还要通过插入null值代替缺失的结点。所以存储为ABCD null EF null G。如果空结点很多的时候，可想这样的存储效率是很低的。所以在存储一个完全二叉树的时候，效率很高。 在学习堆排序的时候，我们知道堆也是一棵树，并且是一个完全二叉树，所以用数组存储的典型实现就是堆。用数组存储不需要节点引用，操作也比较简单。Java中的实现就是PriorityQueue。
链表存储
用链表的形式，我们很好想怎么存储，只要在每个结点存储子节点的引用即可。如果是二叉树，我们可以只存储左结点和右结点，如果是多叉树，我们可以使用一个数组存储每一个子节点。在链表存储的基础上，有很多常用的实现，比如二叉搜索树、AVL 树、红黑树、区间树等。
树的遍历
我们找到在一颗树上的制定结点呢，显然需要遍历树上的所有结点。如果是数组存储，我们遍历这个数组即可。如果是链表存储呢，这时就用两种遍历方式可以选择深度优先遍历DFS和广度优先遍历BFS。DFS深度优先搜索
深度优先，即先往深处找到叶子结点。我们输出一棵树，面对根节点、左子树、右子树，我们有三种输出顺序，就是根左右、左根右、左右根。也叫做前序遍历、中序遍历、后序遍历。对于上面的树，我们使用深度优先，分别使用三种遍历方式遍历结果如下：
- 前序遍历 ：先输出根节点，再输出其左结点，到达左结点因为又是一颗树，再输出其根节点。循环直到处理完根节点所有左子树，再输出右结点，同样方式处理。就是FCADBEHGM
- 中序遍历 ：一直往下找左子树，找到输出A，A代表的树输出完了，退回A的父节点C，因为左结点已经输出完毕，输出根节点C。再找右子树D。同样一直找他的左子树，循环上面的步骤。就是ADBDFHEMG
- 后序遍历 ：同样找左子树，输出A，A代表的树输出完了，退回C，因为要先输出右子树，到了右子树D，同样先找左子树，再找右子树，最后输出根结点。就是ABDCHMGEF
语言描述比较乏力，我们直接上代码
前序遍历
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
if(root == null) return;
Log.d(root.val);
traverse(root.left)；
traverse(root.right)；
}
中序遍历
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
if(root == null) return;
traverse(root.left);
Log.d(root.val);
traverse(root.right);
}
后序遍历
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
if(root == null) return;
traverse(root.left);
traverse(root.right);
Log.d(root.val);
}
上面我们使用递归完成了遍历，同样我们可以使用栈完成遍历，大家可以想想怎么实现，后面的文章会介绍使用栈实现DFS。
BFS广度优先搜索
广度优先，即先往广的方向遍历，也就是优先访问没一个节点的所有子节点，对于一颗树，很形象的解释就是层序遍历，一层一层的访问。对于上面这棵树，BFS的结果就是FCEADHG null null B null nullnull M （空节点使用null标注）。 我们怎么用代码实现呢
可以先自己想想 我们可以使用队列的属性，即先进先出，先放入根节点，取出，放入左右子节点，循环操作取出，放入左右节点。这样就完成了层序遍历。
层序遍历代码
class TreeNode {
int val;
TreeNode left, right;
}
public ArrayList<Integer> printBFS(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null){
return list;
}
//使用队列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
//取出放入左右子树
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
list.add(treeNode.val);
}
return list;
}
常用解题框架
大部分的二叉树题目都是遍历的问题，也就是增删改查的问题，根本方式也就上面的两种DFS和BFS。
BFS也就是上面的方式，使用队列操作数据。
-
DFS也一般使用递归来解决，递归的操作比较难想，一般解题分为三步曲：
- 要处理的子问题是什么？怎么分解成子问题？
- 返回值是什么，每一级递归应该向上返回什么信息？
- 终止条件是什么？什么时候递归到头了？
其实递归就是大量的调用自身的重复操作，所以我们需要把这个大的问题分解成子问题，然后调用自身肯定有一个头，不能无限调用，它的终止条件是什么。还有每一个子问题的数据怎么合并，也就是怎么处理每一个子问题的数据结果。
上面的总结可能还是云里雾里，以后的每日一题中，会先从简单难度的二叉树题目开始，再到中级和高级，慢慢的就会理解这套框架了。
- END -
