import java.util.Stack;class Solution {    private static void doPre(ListNode root) {        if (root == null) {            return;        }        Stack
     
       stack = new Stack<>();        stack.push(root);        while (! stack.isEmpty()) {            ListNode top = stack.pop();            System.out.println(top);            if (top.right != null) {                stack.push(top.right);            }            if (top.left != null) {                stack.push(top.left);            }        }//        System.out.println(root);//        doPre(root.left);//        doPre(root.right);    }    private static void doBehind(ListNode root) {        if (root == null) {            return;        }        Stack
      
        stack = new Stack<>();        stack.push(root);        while (! stack.isEmpty()) {            ListNode top = stack.pop();            if (top.right != null) {                stack.push(top.right);            }            if (top.left != null) {                stack.push(top.left);            }            System.out.println(top);        }//        doBehind(root.left);//        doBehind(root.right);//        System.out.println(root);    }    private static void doMid(ListNode root) {        if (root == null) {            return;        }        Stack
       
         stack = new Stack<>();        while (! stack.isEmpty() || root != null) {            if (root != null) {                stack.push(root);                root = root.left;            } else {                root = stack.pop();                System.out.println(root);                root = root.right;            }        }//        doMid(root.left);//        System.out.println(root);//        doMid(root.right);    }    public static void main(String[] args) {        ListNode n1 = new ListNode(1);        ListNode n2 = new ListNode(2);        ListNode n3 = new ListNode(3);        ListNode n4 = new ListNode(4);        ListNode n5 = new ListNode(5);        ListNode n6 = new ListNode(6);        ListNode n7 = new ListNode(7);        ListNode n8 = new ListNode(8);//        n1.next = n2;//        n2.next = n3;//        n3.next = n4;//        n4.next = n5;//        n5.next = n6;//        n6.next = n7;//        n7.next = n8;        n1.left = n2;        n1.right = n3;        n2.left = n4;        n2.right = n5;        n3.left = n6;        n3.right = n7;        n5.left = n8;        doMid(n1);    }}class ListNode {    int val;    ListNode left;    ListNode right;    ListNode(int x) { val = x; }    @Override    public String toString() {        return "ListNode{" +                "val=" + val +                '}';    }}