二叉树的前序、中序、后序、层序遍历（递归和非递归）

一、节点定义：

package BinaryTreeTraversal;

//二叉树的节点类型
public class TreeNode{
    int val;   //节点值
    TreeNode left;  //左孩子
    TreeNode right; //右孩子
    public TreeNode(int val) {
        this.val=val;
    }
}

二、递归实现前序、中序、后序遍历：

package BinaryTreeTraversal;

import java.util.ArrayList;

//递归实现
public class RecursiveSolution {
    private ArrayList<Integer> rel = new ArrayList<>();//存放遍历结果

    //前序遍历
    public void preOrder(TreeNode root){
        if(root == null)
            return;

        rel.add(root.val);//当前节点先遍历
        preOrder(root.left);//再递归遍历其左子节点
        preOrder(root.right);//再递归遍历其右子节点
    }

    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null)
            return;

        inOrder(root.left);
        rel.add(root.val);
        inOrder(root.right);
    }

    //后续遍历
    public void postOrder(TreeNode root){
        if(root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        rel.add(root.val);
    }
}

三、非递归实现前序、中序、后序遍历：

package BinaryTreeTraversal;

import java.util.ArrayList;
import java.util.Stack;

//非递归实现
public class NonRecursiveSolution {
    private ArrayList<Integer> rel = new ArrayList<>();//存放遍历结果

    //前序遍历（一定先将右子节点入栈，再将左子节点入栈）
    public void preOrder(TreeNode root){
        if(root == null)
            return;
        Stack<TreeNode> stack = new Stack<>();//辅助栈
        stack.push(root);//根节点先入队
        while(!stack.isEmpty()){
            TreeNode curNode = stack.pop();//取栈顶节点
            rel.add(curNode.val);//将栈顶节点值添加进遍历结果列表
            if(curNode.right != null){
                stack.push(curNode.right);//若当前节点的右子节点不为空，则右子节点进栈
            }
            if(curNode.left != null){
                stack.push(curNode.left);//若当前节点的左子节点不为空，则左子节点进栈
            }
        }
    }

    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null)
            return;
        Stack<TreeNode> stack = new Stack<>();//辅助栈
        TreeNode curNode = root;
        while(curNode != null || !stack.isEmpty()){
            //先将"最左边"节点入栈
            while(curNode != null){
                stack.push(curNode);
                curNode  = curNode.left;
            }
            curNode = stack.pop();//访问栈顶元素
            rel.add(curNode.val);//将当前遍历出来的节点值添加进遍历结果列表
            //若当前节点有右子节点，则将右子节点赋值给curNode，即下一步将右子节点入栈
            //若当前节点不存在右子节点，则下一步将访问栈顶元素
            curNode = curNode.right;
        }
    }

    //后序遍历
    public void postOrder(TreeNode root){
        if(root == null)
            return;
        Stack<TreeNode> stack = new Stack<>();//辅助栈
        TreeNode curNode = root;
        TreeNode preNode = null;//前一个访问的节点
        while(curNode != null || !stack.isEmpty()){
            while(curNode != null){
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();//取栈顶元素

            if(curNode.right == null || preNode == curNode.right){
                //若curNode右子节点为空或者上一个访问的节点是其右子节点，则将curNode值添加进遍历结果列表
                rel.add(curNode.val);
                preNode = curNode;
                curNode = null;//表明下一次取栈顶元素
            }else{
                //若curNode的右子节点不为空，且上一次访问的节点不是其右子节点
                stack.push(curNode);//则将当前节点重新入栈
                curNode = curNode.right;//先遍历其右子树
            }

        }
    }
}

四、层序遍历的简单和复杂实现：

package BinaryTreeTraversal;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

//层序遍历实现
public class LevelOrderSolution {
    private ArrayList<Integer> rel1 = new ArrayList<>();//存放简单层序遍历结果
    private ArrayList<ArrayList<Integer>> rel2 = new ArrayList<>();//存放复杂层序遍历结果

    //简单层序遍历，逐层打印即可
    public void simpleLevelOrder(TreeNode root){
        if(root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();//辅助队列
        queue.offer(root);//根节点入队
        while(!queue.isEmpty()){
            TreeNode curNode = queue.poll();//取队首节点
            rel1.add(curNode.val);
            if(curNode.left != null){
                queue.offer(curNode.left);
            }
            if(curNode.right != null){
                queue.offer(curNode.right);
            }
        }
    }

    //复杂层序遍历，一层打印一行
    public void hardLevelOrder(TreeNode root){
        if(root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();//辅助队列
        ArrayList<Integer> list = new ArrayList<>();//打印每一行的结果
        queue.offer(root);//根节点先入队
        while(!queue.isEmpty()){
            int size = queue.size();//获取当前行的大小
            //逐行输出
            for(int i=0; i<size; i++){
                TreeNode curNode = queue.poll();
                list.add(curNode.val);//将当前节点值添加到该行结果列表中
                if(curNode.left != null){
                    queue.offer(curNode.left);//非空左子节点入队
                }
                if(curNode.right != null){
                    queue.offer(curNode.right);//非空右子节点入队
                }
            }
            //将非空行的遍历结果添加到最终的结果列表中
            if(list.size() != 0){
                rel2.add(list);
            }
            list = new ArrayList<>();//很重要，一定要重新初始化一个list！！！！
        }
    }
}