大家好，我是热心的大肚皮，皮哥。以后我们又多了一个算法系列，会带着大家一起向着成神之路迈进。
什么是二叉树？
简单介绍下，二叉树是一种典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作左子树和右子树。如下图。
最好情况下的算法时间复杂度为O(1)，最坏情况下的算法时间复杂度为O(n)。
二叉树如何遍历？
二叉树的基本遍历方式有4种，即前序遍历、中序遍历、后序遍历以及层序遍历。
- 前序遍历
按照根节点 -> 左孩子 -> 右孩子 的方式遍历，每次先遍历根节点，遍历结果为 1 2 4 5 3 6 7；直接上代码。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
getNodeVal(list, root);
return list;
}
public void getNodeVal(List<Integer> list, TreeNode root){
//如果没有节点直接返回
if (null == root){
return;
}
//前序遍历先添加 根->左->右 ，所以先添加根的值
list.add(root.val);
//递归查询先添加左节点
getNodeVal(list, root.left);
//递归查询先添加右节点
getNodeVal(list, root.right);
}
- 中序遍历
按照 左孩子-> 根节点 -> 右孩子 的方式遍历，每次先遍历左孩子，遍历结果为 4 2 5 1 6 3 7；直接上代码。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
getNodeVal(list, root);
return list;
}
public void getNodeVal(List<Integer> list, TreeNode root){
if (null == root){
return;
}
//前序遍历先添加 左->根->右 ，所以先添加左孩子的值
getNodeVal(list, root.left);
list.add(root.val);
getNodeVal(list, root.right);
}
- 后序遍历
按照 左孩子-> 右孩子 -> 根节点 的方式遍历，每次先遍历左孩子，遍历结果为 4 5 2 6 7 3 1；直接上代码。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
getNodeVal(list, root);
return list;
}
public void getNodeVal(List<Integer> list, TreeNode root){
if (null == root){
return;
}
//前序遍历先添加 左->右->根 ，所以先添加左孩子的值
getNodeVal(list, root.left);
getNodeVal(list, root.right);
list.add(root.val);
}
- 层级遍历
层次遍历就是按照每一层从左向右的方式进行遍历，每次先遍历左孩子，遍历结果为 1 2 3 4 5 6 7；
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> listResult = new ArrayList<>();
if (null == root) {
return listResult;
}
//声明一个队列
Queue<TreeNode> treeNodeQueue = new LinkedList<>();
//将头节点放入队列，此处用offer
//offer，add 区别：
//一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，
//多出的项就会被拒绝。这时新的 offer 方法就可以起作用了。
//它不是对调用 add() 方法抛出一个 unchecked 异常，
//而只是得到由 offer() 返回的false。
treeNodeQueue.offer(root);
//while每次循环都是操作一个层级的节点。
while (!treeNodeQueue.isEmpty()) {
//获取队列的长度
int size = treeNodeQueue.size();
List<Integer> list = new ArrayList<>(size);
//此处注意，只操作删除每个层级的节点，所以是1->size
for (int i = 1; i <= size; ++i) {
//poll，remove 区别：
// remove()和poll()方法都是从队列中删除第一个元素。
// remove()的行为与 Collection 接口的版本相似，但是
// 新的poll()方法在用空集合调用时不是抛出异常，只是返回
// null。因此新的方法更适合容易出现异常条件的情况。
TreeNode temp = treeNodeQueue.poll();
if (temp == null) {
break;
}
//添加当前层级节点值
list.add(temp.val);
//将当前节点加入队列中。
if (temp.left != null) {
treeNodeQueue.offer(temp.left);
}
if (temp.right != null) {
treeNodeQueue.offer(temp.right);
}
}
listResult.add(list);
}
return listResult;
}
以上就是4种基本的遍历方式，看到这里大家是不是发现，所谓的就是前中后指的是根结点的位置，层级遍历这种思路也可以应用在查询二叉树的深度。
