知识点：

遍历二叉树，可有3+1种方法：先序、中序、后序和层次法。
以下前三种方法从根部开始逆时针方向绕过各结点，形成一条蜿蜒“足迹”。

(1)先序法（又称先根法）
先序遍历：根，左子树，右子树
遍历的结果：A，B，C
遍历的足迹：沿途经过各结点的“左部”

(2)中序法（又称中根法）
中序遍历：左子树，根，右子树
遍历的结果：B，A，C
遍历的足迹：沿途经过各结点的“下部”

(3)后序法（又称后根法）
后序遍历：左子树，右子树，根
遍历的结果：B，C，A
遍历的足迹：沿途经过各结点的“右部”

(4)层次法
层次遍历：从根开始，层次自上到下，同层结点自左至右进行。
遍历的结果：A，B，C
遍历的足迹：第一层A，第二层B，C


代码实现：

递归方法

//递归序  每个节点都会遍历三次 ： 124666477742555213888399931
    public static void f(TreeNode root){
        if(root==null) return;
        System.out.print(root.val);
        f(root.left);
        System.out.print(root.val);
        f(root.right);
        System.out.print(root.val);
    }
    //先序遍历 取递归序 每个节点出现第一次 124675389 --深度遍历
    public static void preorder(TreeNode root){
        if(root==null) return;
        System.out.print(root.val);
        preorder(root.left);
        preorder(root.right);
    }
    //中序遍历 取递归序 每个节点出现第二次647251839
    public static void midorder(TreeNode root){
        if(root==null) return;
        midorder(root.left);
        System.out.print(root.val);
        midorder(root.right);
    }
    //后序遍历 取递归序 每个节点出现第三次  674528931
    public static void posorder(TreeNode root){
        if(root==null) return;
        posorder(root.left);
        posorder(root.right);
        System.out.print(root.val);
    }

非递归方法

//非递归 先序 构建一个栈 存入头结点 当栈不为空 输出栈顶节点 当这个节点有左右节点 不为空 右左存储
    public static void preorder1(TreeNode root){
        Stack<TreeNode> s =new Stack<>();
        s.push(root);
        while (!s.empty()){
            TreeNode t =s.pop();
            System.out.print(t.val);
            if(t.right!=null) s.push(t.right);
            if(t.left!=null) s.push(t.left);
        }
    }
    //非递归 中序 构建一个栈 先将树的所有左节点压入 （根节点也算） 遇到左节点为空 开始进行出栈 并且出栈节点要是有右节点就压入
    public static void midoder1(TreeNode root){
        Stack<TreeNode> s =new Stack<>();
        while (!s.empty()|| root!=null){
            if(root!=null){
                s.push(root);
                root=root.left;
            }
            else {
                root =s.pop();
                System.out.println(root.val);
                root =  root.right;
            }
        }
    }
    //非递归 后续序 构建两个栈  存入头结点 当栈不为空 输出栈顶节点到第二个栈 当这个节点有左右节点 不为空 左右存储  先序 头左右-》 头右左 调换左右放进去的顺序 最后结果进行反转
    public static void posorder1(TreeNode root){
        Stack<TreeNode> s =new Stack<>();
        s.push(root);
        List<Integer> list =new ArrayList<>();
        while (!s.empty()){
            TreeNode t =s.pop();
            list.add(t.val);
            if(t.left!=null) s.push(t.left);
            if(t.right!=null) s.push(t.right);
        }
        Collections.reverse(list);
        for (Integer integer : list) {
            System.out.print(integer);
        }
    }
    //非递归层次遍历 将每一层的输出 从左到右  宽度遍历
    public static void preorder2(TreeNode root){
        Queue <TreeNode> q =new LinkedList<>();
        q.offer(root);
        int n = q.size();
        while (!q.isEmpty()){
            if(q.size()>n) n=q.size();//求宽度
            for (int i = q.size(); i >0; i--) {
                TreeNode t =q.poll();
                System.out.print(t.val);
                if(t.left!=null) q.add(t.left);
                if(t.right!=null) q.add(t.right);
            }
        }
        System.out.println(n);
    }