非递归

 //先序遍历
 public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.println("binary tree pre order traverse: ");
        Stack<TreeNode> stack = new Stack<>();// 通过栈结构，来保存访问信息
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();// 当前节点从栈中弹出即访问它
            System.out.println("cur = " + root.value);// 打印节点信息
            if (root.right != null) {// 因为栈的后进先出特性，我们会把右节点先入栈，保证它在左节点访问之后再访问
                stack.push(root.right);
            }
            if (root.left != null) {// 左节点后压栈，先弹出，保证了 父节点->左节点->右节点的访问顺序
                stack.push(root.left);
            }
        }
    }

//中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) return;
        System.out.println("binary tree in order traverse: ");
        Stack<TreeNode> stack = new Stack<>();// 同样需要一个栈来辅助操作,相比于先序遍历，不会先压栈
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;// 如果节点存在左子节点，会一直先将左子节点压栈，直到没有左节点为止
            } else {// 如果当前遍历到的节点没有左子节点了，就弹栈，开始访问左节点
                root = stack.pop();
                System.out.println("val = " + root.value);// 访问节点信息并打印
                root = root.right;// 因为当前节点无左子节点，当前指针会往右子节点前进，然后循环这个过程
            }
        }
    }
//后序遍历
  public void postOrder(TreeNode root) {
        if (root == null) return;
        System.out.println("binary tree post order traverse: ");
        Stack<TreeNode> stack1 = new Stack<>();// 后序遍历需要两个栈
        Stack<TreeNode> stack2 = new Stack<>();// 用来倒置先序遍历的结果
        stack1.push(root);
        while (!stack1.isEmpty()) {
            root = stack1.pop();
            stack2.push(root);
            if (root.left != null) {// 注意这里与先序遍历不同的在于是先将左节点压栈，即在这里使左右节点的访问顺序互换
                stack1.push(root.left);
            }
            if (root.right != null) {
                stack1.push(root.right);
            }
        }
        while (!stack2.isEmpty()) {// 利用栈的后进先出特性，将先序的整个遍历结果倒置，即得到我们想要的后序遍历结果
            System.out.println(stack2.pop().value + " ");
        }
    }
    
//层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) return;
        System.out.println("binary tree level traverse: ");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            root = queue.poll();// 先进队列的节点先弹出，先访问
            System.out.print(root.val + " ");
            if (root.left != null) {// 每一个父节点会有左右两个子节点，层次遍历即先访问父节点，然后按从左到右顺序依次访问左右子节点。
                queue.offer(root.left);// 左子节点进队列，下一轮循环，即先弹出左子节点，再将左子节点的左右子节点入队列，如此循环，即可实现按层访问所有节点。
            }
            if (root.right != null) {
                queue.offer(root.right);// 右子节点进队列，
            }
        }
        System.out.println();
    }