1、背景
二叉树作为一个重要的数据结构，在实际生产应用中有很多的应用。那么掌握其遍历的方式对实际生产以及了解源码都很有益。
2、遍历方式
二叉树的主要遍历方式有4种：先序、中序、后序以及层序遍历
首先，声明一下节点TreeNode类，如下：
package com.kunkun.offer.show.common;
/**
* @author: liukun
* @Date: 2021/11/21
*/
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
2.1、先序遍历
先序遍历的遍历顺序：根 、左、右。
也就是说前序遍历就是先访问根节点，再访问左节点，最后访问右节点。
例：如图
image
我们按照先序遍历的访问顺序遍历这个二叉树得到的结果：3、9、20、15、7
在实际应用中，先序遍历主要有两种实现方式：递归和栈
具体实现：java
- 首先是递归的实现，递归的实现其实很简单。递归出口是当前节点是null的话，结束递归。先访问当前节点，依次访问左右节点就好了。
/**
* 先序遍历:根左右
*
* 递归
* @param root
*/
public void preTraversal(TreeNode root){
//递归出口
if(null == root) {
return;
}
System.out.println(root.val);
preTraversal(root.left);
preTraversal(root.right);
}
- 栈的先序遍历实现
/**
* 先序遍历
*
* 栈
* @param root
*/
public void preTraversal2(TreeNode root){
//递归出口
if(null == root) {
return;
}
//初始化栈
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
//如果p不为空，栈非空。进入循环
while (null != p || !stack.isEmpty()){
if (p != null) {
System.out.println(p.val);
stack.push(p);
p = p.left;
} else {
p = stack.pop();
p = p.right;
}
}
}
2.2、中序遍历
中序遍历的遍历顺序：左、根、右。
也就是说前序遍历就是先访问左子树，再访问根节点，最后访问右节点。
同样是上面那棵树，他的中序遍历是：9、3、15、20、7
具体实现：java
- 递归实现
/**
* 中序便利的递归实现：左根右
*
* @param root
*/
public void inTraversal(TreeNode root) {
if (null == root) {
return;
}
inTraversal(root.left);
System.out.println(root.val);
inTraversal(root.right);
}
- 栈实现
/**
* 中序遍历的栈实现
* @param root
*/
public void inTraversal2(TreeNode root) {
if (null == root) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
//循环条件
while(null != p || !stack.isEmpty()){
if (p != null) {
stack.push(p);
p = p.left;
} else {
p = stack.pop();
System.out.println(p.val);
p = p.right;
}
}
}
2.3、后序遍历
中序遍历的遍历顺序：左、右、根。
也就是说前序遍历就是先访问左子树，再访问右节点，最后访问根节点。
同样是上面那棵树，他的中序遍历是：9、15、7、20、3
具体实现：java
- 递归实现
/**
* 二叉树后序遍历的递归实现：左右根
*
* @param root
*/
public void postorderTraversal(TreeNode root){
if (null == root) {
return;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.println(root.val);
}
- 栈实现(先序遍历的变种、很多人使用的方法)
- 个人认为遍历算法的核心，其实是节点访问的次序，用这种方法，其实思想依然是先序遍历的，并不是真正后序遍历。
/**
* 后序遍历栈实现:
*
* 失去遍历算法核心的实现方法
* @param root
*/
public void postorderTraversal2(TreeNode root){
if (null == root) {
return;
}
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new LinkedList<>();
TreeNode p = root;
while(null != p || !stack.isEmpty()) {
if (null != p) {
list.add(p.val);
stack.push(p);
p = p.right;
}else {
p = stack.pop();
p = p.left;
}
}
Collections.reverse(list);
}
- 栈实现（重要）
/**
* 真正的后序遍历的栈实现
*
* 遍历算法的核心是内存的读取顺序
*
* 要熟练掌握这种方式
*
* @param root
*/
public void postorderTraversal3(TreeNode root){
if (null == root) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
TreeNode prev = null;
List<Integer> result = new LinkedList<>();
while (null != p || !stack.isEmpty()) {
while(p != null){
stack.push(p);
p = p.left;
}
p = stack.pop();
if (null == p.right || prev == p.right) {
result.add(p.val);
prev = p;
p = null;
} else {
stack.push(p);
p = p.right;
}
}
}
2.4、层序遍历
层序遍历是将二叉树每一层从左到右访问
接上面的例子，访问顺序为：3、9、20、15、7
具体实现：java
- 队列的方式
/**
* 二叉树的层序遍历
*
* @param root
* @return
*/
public static List<Integer> levelOrder(TreeNode root) {
if (null == root) {
return new LinkedList<>();
}
List<TreeNode> queue = new LinkedList<>();
TreeNode p = root;
queue.add(p);
List<Integer> result = new LinkedList<>();
while(queue.size() != 0){
p = queue.remove(0);
result.add(p.val);
if (p.left != null) {
queue.add(p.left);
}
if (p.right != null) {
queue.add(p.right);
}
}
return result;
}
3、总结
二叉树的遍历是数据结构中非常重要的一章，先序、中序、后序对应的递归和栈的实现方式需要熟练掌握。尤其后续的栈实现，比较复杂。
