目录
二叉树是一种重要的数据结构，其遍历方式分为：深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即就是层次遍历。如下图：
class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(){
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
1、前序遍历
遍历顺序：根节点—左子树—右子树
如上图，遍历结果应该为：12457836
（1）递归实现前序遍历
/**
* 递归实现前序遍历
* @param treeNode 树的根节点
*/
public static void preOrder1(TreeNode treeNode){
// 若根节点为空，直接返回
if(treeNode == null){
return;
}
//打印根节点
System.out.print(treeNode.val + "\t");
// 遍历根节点的左子树
preOrder1(treeNode.left);
// 遍历根节点的右子树
preOrder1(treeNode.right);
}
（2）非递归实现前序遍历
非递归实现可以通过辅助栈或者辅助队列实现。以下代码为辅助栈的实现方式：
/**
* 非递归实现前序遍历
* @param treeNode 根节点
*/
public static void preOrder2(TreeNode treeNode){
// 如果根节点为空，直接返回。
if(treeNode == null){
return;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
// 根节点入栈
stack.push(treeNode);
// 当栈不为空
while(!stack.isEmpty()){
//取出栈顶元素
TreeNode node = stack.pop();
//打印根节点
System.out.print(node.val + "\t");
// 如果使用的是辅助栈，则先将根节点的右子节点入栈；如果是辅助队列，则先将根节点的左子节点入队列。因为栈是先进后出，队列是先进入=先出
if(node.right != null){
stack.push(node.right);
}
// 根节点的右子节点入栈
if(node.left != null){
stack.push(node.left);
}
}
}
2、中序遍历
遍历顺序：左子树—根节点—右子树
如上图，遍历结果应该为：42758136
（1）递归实现中序遍历
/**
* 递归实现中序遍历
* @param treeNode 树的根节点
*/
public static void inOrder1(TreeNode treeNode){
// 若根节点为空，直接返回
if(treeNode == null){
return;
}
// 遍历根节点的左子树
inOrder1(treeNode.left);
//打印根节点
System.out.print(treeNode.val + "\t");
// 遍历根节点的右子树
inOrder1(treeNode.right);
}
（2）非递归实现中序遍历
/**
* 非递归实现中序遍历
* @param treeNode 根节点
*/
public static void inOrder2(TreeNode treeNode){
// 如果根节点为空，直接返回。
if(treeNode == null){
return;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
// 临时指针
TreeNode cur = treeNode;
// 当栈不为空
while(cur != null || !stack.isEmpty()){
// 左节点入栈
while(cur != null){
stack.push(cur);
cur = cur.left;
}
//取出栈顶元素
cur = stack.pop();
//打印左节点
System.out.print(cur.val + "\t");
// 指向右节点
cur = cur.right;
}
}
3、后序遍历
遍历顺序：左子树—右子树—根节点
如上图，遍历结果应该为：47852631
（1）递归实现后序遍历
/**
* 递归实现后序遍历
* @param treeNode 树的根节点
*/
public static void postOrder1(TreeNode treeNode){
// 若根节点为空，直接返回
if(treeNode == null){
return;
}
// 遍历根节点的左子树
postOrder1(treeNode.left);
// 遍历根节点的右子树
postOrder1(treeNode.right);
//打印根节点
System.out.print(treeNode.val + "\t");
}
（2）非递归实现后序遍历
/**
* 非递归实现后序遍历
* @param treeNode 根节点
*/
public static void postOrder2(TreeNode treeNode){
// 如果根节点为空，直接返回。
if(treeNode == null){
return;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
// 临时指针
TreeNode cur = treeNode, pre = null;
// 当栈不为空
while(cur != null || !stack.isEmpty()){
// 左节点入栈
while(cur != null){
stack.push(cur);
cur = cur.left;
}
//取出栈顶元素
cur = stack.get(stack.size()-1);
if(cur.right == null || pre == cur.right){
stack.pop();
System.out.print(cur.val + "\t");
pre = cur;
cur = null;
}else{
// 指向右节点
cur = cur.right;
}
}
}
4、层序遍历
遍历顺序：逐层遍历
如上图，遍历结果应该为：12345678。通过辅助队列，在取出节点的同时，将当前节点的左右节点分别入队。
/**
* 层序遍历
* @param treeNode
*/
public static void levelOrder(TreeNode treeNode){
//根节点为空，直接返回
if(treeNode == null){
return;
}
//辅助队列
Queue<TreeNode> queue = new LinkedList<>();
//根节点入队列
queue.offer(treeNode);
//当栈不为空
while(!queue.isEmpty()){
//取出队首元素
TreeNode node = queue.poll();
System.out.print(node.val + "\t");
//将节点的左节点入队
if(node.left != null){
queue.offer(node.left);
}
//节点的右节点入队
if(node.right != null){
queue.offer(node.right);
}
}
}
5、之字形遍历
这是牛客上的一道题。这个之字形遍历也可理解为Z字形遍历，以上树为例，其遍历结果为：1，3，2，4，5，6，8，7。本质还是二叉树的层序遍历，只不过在便利的时候，要将偶数层的节点逆序。
代码：
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
//存储结果
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
//如果根节点为空，则直接返回
if(root == null){
return result;
}
//辅助队列
Queue<TreeNode> queue = new LinkedList<>();
//根节点入队
queue.offer(root);
//是否转向
boolean flag = false;
while(!queue.isEmpty()){
//获取队列长度
int size = queue.size();
//存储每一层的遍历结果
ArrayList<Integer> list = new ArrayList<>();
for(int i=0; i < size; i++){
//取出队列元素
TreeNode node = queue.poll();
if(node == null){
continue;
}
if(!flag){
list.add(node.val);
}else{
list.add(0, node.val);
}
//左右节点各入队
queue.offer(node.left);
queue.offer(node.right);
}
//如果有值，存入结果集
if(list.size() > 0){
result.add(list);
}
//转向
flag = !flag;
}
return result;
}
}
版权声明：本文为weixin_47382783原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。