二叉树层序、前中后序遍历（递归、迭代）

        二叉树的遍历经常在笔试或者面试的时候需要遇到，本文实现了二叉树的前中后序的递归与迭代两种算法、层序遍历使用迭代的方式实现了单个list场景以及双重list场景的实现方式。

package t1;

import java.util.*;

public class LevelOrder {
	ArrayList> list = new ArrayList<>(); 
	
	//前中后遍历  递归调用
	public static void order(TreeNode root,Queue queue){
		if(root == null) {
			return;
		}
    //前序遍历
		queue.add(root.val);
		order(root.left,queue);
    //中序遍历
        //queue.add(root.val);
        order(root.right,queue);
    //后序遍历
        //queue.add(root.val);
        
	}
	
	//前序遍历迭代
	public static ArrayList preOreder(TreeNode root){
		if(root == null) {
			return null;
		}
		Stack stack = new Stack<>();
		ArrayList list = new ArrayList<>();
		stack.add(root);
		while(!stack.isEmpty()) {
			root = stack.pop();
			list.add(root.val);
			if(root.right != null) {
				stack.push(root.right);
			}
			if(root.left != null) {
				stack.push(root.left);
			}
		}
		return list;
	}
	//中序遍历
	public static ArrayList midOrder(TreeNode root){
		ArrayList list = new ArrayList<>();
		Stack stack = new Stack<>();
		while(!stack.isEmpty() || root != null) {
			if(root != null) {
				stack.push(root);
				root = root.left;
			}else {
				root = stack.pop();
				list.add(root.val);
				root = root.right;
			}
		}
		return list;
	}
	
	//后序遍历
	public static ArrayList postOrder(TreeNode root){
		
		ArrayList list = new ArrayList<>();
		Stack stack = new Stack<>();
		TreeNode pre = null;
		while(!stack.isEmpty()||root != null ) {
			while(root != null) {
				stack.push(root);
				root = root.left;
			}
		
		root = stack.pop();
		if(root.right == null || root.right == pre) {
			list.add(root.val);
			pre = root;
			root = null;
		}else {
			stack.push(root);
			root = root.right;
		}
		}
		return list;
		
	}
	//层序遍历 双重list（迭代）
    public static ArrayList> levelOrder(TreeNode root){
    	ArrayList> list = new ArrayList<>();
    	Queue queue = new LinkedList<>();
    	if(root == null) {
    		return null;
    	}
    	queue.add(root);
    	while(!queue.isEmpty()) {
    		int size = queue.size();
    		ArrayList temp = new ArrayList<>();
    		for(int i = 0; i < size; i++) {
    			TreeNode node= queue.poll();
    			temp.add(node.val);
    			if(node.left != null) {
    				queue.add(node.left);
    			}
    			if(node.right != null) {
    				queue.add(node.right);
    			}
    		}
    		list.add(temp);
    	}
		return list;
    }
    //层序遍历  单个list返回(迭代)
    public static ArrayList or(TreeNode root){
    	if(root == null) {
    		return null;
    	}
    	ArrayList list = new  ArrayList<>();
    	Queue queue = new LinkedList<>();
    	queue.add(root);
    	while(!queue.isEmpty()) {
    		TreeNode node = queue.poll();
    		list.add(node.val);
    		if(node.left != null) {
    			queue.add(node.left);
    		}
    		if(node.right != null) {
    			queue.add(node.right);
    		}
    	}
		return list;
    	
    }
    public static void main(String[] args) {
        //创建二叉树
        TreeNode t = new TreeNode(1);
        t.left = new TreeNode(2);
        t.right = new TreeNode(3);
        t.left.left = new TreeNode(4);
        t.left.left.right = new TreeNode(5);
        t.right.left = new TreeNode(6);
        t.right.right = new TreeNode(7);
        //执行层序遍历方法
//        ArrayList>  lists = LevelOrder.levelOrder(t);
//        
//        System.out.println(lists);
//        ArrayList lis = or(t);
//        System.out.println(lis);
//        Queue q = new LinkedList<>();
//        LevelOrder.order(t, q);
//        System.out.println(q);
//        ArrayList list2 = preOreder(t);
//        System.out.println(list2);
        
//        ArrayList list3 = midOrder(t);
//        System.out.println(list3);
        
        ArrayList list4 = postOrder(t);
        System.out.println("4"+list4);
        
	}
}


class TreeNode {
    int val; //结点值
    TreeNode left; //左子树结点
    TreeNode right; //右子树结点

    public TreeNode(int val) {
        this.val = val;
    }
}