文章目录
前言
一、二叉树的前序遍历
1.1 递归算法
1.2 非递归算法
二、二叉树的中序遍历
2.1 递归算法
2.2 非递归算法
三、二叉树的后序遍历
3.1 递归算法
3.2 非递归算法
四、二叉树的层序遍历
总结
前言
最近一直在学习数据结构，学习的过程中不禁感叹编程真是一个神奇的东西，当我学习完二叉树后，彻底拜倒在递归的石榴裙下，脑子里只剩下一句话——多么神奇的递归啊！这让我不得不浅浅的记录一下。
一、二叉树的前序遍历
144. 二叉树的前序遍历
前序遍历：“根左右”——先访问根节点，在访问左子树，最后访问右子树。
图解：
前序遍历序列为：ABDGHCEIF
1.1 递归算法
先访问根节点，递归访问左子树，递归访问右子树：
import java.util.ArrayList;
import java.util.List;
public class Num144_preorderTraversal {
List list=new ArrayList<>();
public List preorderTraversal(TreeNode root) {
if (root==null){
return list;
}
list.add(root.val);
//递归遍历左子树
preorderTraversal(root.left);
//递归遍历右子树
preorderTraversal(root.right);
return list;
}
}
1.2 非递归算法
借助栈实现二叉树的前序遍历的非递归算法，第一次走到根节点时就可以访问根节点：
此时先将右孩子压入栈，再将左孩子压入栈，是因为栈是一个后进先出的结构，出栈时就是左孩子先出栈，然后右孩子再出栈。
import java.util.*;
public class Num144_PreorderNonRecursion{
public List preorderTraversal(TreeNode root){
List ret=new ArrayList<>();
if (root==null){
return ret;
}
//借助栈实现
Stack stack=new Stack<>();
//先将根节点入栈
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur=stack.pop();
//将cur.val存入ret
ret.add(cur.val);
//先将右孩子压入栈
if (cur.right!=null){
stack.push(cur.right);
}
//再将左孩子压入栈
if (cur.left!=null){
stack.push(cur.left);
}
}
return ret;
}
}
二、二叉树的中序遍历
94. 二叉树的中序遍历
中序遍历：“左根右”——先访问左子树，然后访问根节点，最后访问右子树。
图解：
中序遍历序列为：GDHBAEICF
2.1 递归算法
先递归访问左子树，然后访问根节点，最后递归访问右子树：
import java.util.ArrayList;
import java.util.List;
public class Num94_inorderTraversal {
List list=new ArrayList<>();
public List inorderTraversal(TreeNode root) {
if (root==null){
return list;
}
//递归遍历左子树
inorderTraversal(root.left);
list.add(root.val);
//递归遍历右子树
inorderTraversal(root.right);
return list;
}
}
2.2 非递归算法
借助栈实现二叉树的中序遍历的非递归算法，第二次走到根节点时才能访问：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Num94_InorderNonRecursion {
public List inorderTraversal(TreeNode root) {
List ret=new ArrayList<>();
if (root==null){
return ret;
}
TreeNode cur=root;
Stack stack=new Stack<>();
while(!stack.isEmpty()||cur!=null){
//一直走左子树，直到遇到没有左子树的结点
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
//然后将那个没有左子树的节点出栈，存入ret
cur=stack.pop();
ret.add(cur.val);
//访问它的右子树
cur=cur.right;
}
return ret;
}
}
三、二叉树的后序遍历
144. 二叉树的前序遍历
后序遍历：“左右根”——先访问左子树，然后访问右子树，最后访问根节点。
图解：
后序遍历序列为：GHDBIEFCA
3.1 递归算法
先递归访问左子树，然后递归访问右子树，最后访问根节点：
public class Num145_postorderTraversal {
List list=new ArrayList<>();
public List postorderTraversal(TreeNode root) {
if (root==null){
return list;
}
//先递归访问左子树
postorderTraversal(root.left);
//递归访问右子树
postorderTraversal(root.right);
//访问根节点
list.add(root.val);
return list;
}
}
3.2 非递归算法
借助栈实现二叉树的后序遍历的非递归算法，第三次走到根节点时才能访问：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Num145_PostorderNonRecursion {
public List postorderTraversal(TreeNode root) {
List ret=new ArrayList<>();
if (root==null){
return ret;
}
TreeNode cur=root;
//上一个完全处理过的节点
TreeNode prev=null;
Stack stack=new Stack<>();
while(!stack.isEmpty()||cur!=null){
//一直走左子树，直到遇到第一个没有左子树的节点
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
//此时左树为空，取栈顶元素
cur=stack.pop();
//如果cur的右子树为空或者左子树是上一个处理过的节点
//就将cur.val存入ret，更新prev和cur
if (cur.right==null||prev==cur.right){
ret.add(cur.val);
prev=cur;
cur=null;
}else{
//否则就将cur再入栈，一直访问右子树
stack.push(cur);
cur=cur.right;
}
}
return ret;
}
}
四、二叉树的层序遍历
102. 二叉树的层序遍历
层序遍历：从根节点开始，依次向下，对于每一层从左到右遍历。
图解：
层序遍历序列为：ABCDEFGHI
使用队列来解决问题：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Num102_levelOrder {
public List> levelOrder(TreeNode root) {
List> ret=new ArrayList<>();
if (root==null){
return ret;
}
//使用队列来解决问题
Deque deque=new ArrayDeque<>();
//先将根节点入队
deque.offer(root);
while(!deque.isEmpty()){
//用list来存储每层节点值
List list=new ArrayList<>();
//取得此时队列中的节点个数
int size=deque.size();
//取出此时队列中的节点，将节点值存入list
for (int i = 0; i < size; i++) {
TreeNode cur=deque.poll();
list.add(cur.val);
//判断此节点的左右子树是否为空，不为空将它们分别入队
if (cur.left!=null){
deque.offer(cur.left);
}
if (cur.right!=null){
deque.offer(cur.right);
}
}
ret.add(list);
}
return ret;
}
}
总结
二叉树的遍历看似简单，其实代码越少，其中的步骤越复杂，尤其是三大遍历的递归写法，有时候越简单的东西越容易出错，所以在学习二叉树的遍历的时候，大家一定要认真理解递归的语义，不要过分纠结递归是如何实现的，最重要的是理解！！！
创作不易，你是否有收获呢？如果有收获的话，请留下你的小手手！
