import java.util.*;

public class Test {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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


    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;
        List<Integer> f = in(treeNode1);
        System.out.println(f);
        System.out.println(pre(treeNode1));
        System.out.println(post(treeNode1));
    }

    /**
     * 中序遍历 非递归
     */
    public static List<Integer> in(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode p = root;
        while (p != null || !stk.isEmpty()) {
            while (p != null) {
                stk.push(p);
                p = p.left;
            }
            p = stk.pop();
            res.add(p.val);
            p = p.right;
        }
        return res;
    }

    /**
     * 非递归先序
     */
    public static List<Integer> pre(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        stk.push(root);
        TreeNode p = root;
        while (!stk.isEmpty()) {
            p = stk.pop();
            res.add(p.val);
            if (p.right != null) {
                stk.push(p.right);
            }
            if (p.left != null) {
                stk.push(p.left);
            }

        }
        return res;
    }

    /**
     * 非递归后续遍历
     */
    public static List<Integer> post(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode p = root;
        TreeNode prev = null;
        while (p != null || !stk.isEmpty()) {
            while (p != null) {
                stk.push(p);
                p = p.left;
            }
            p = stk.pop();
            if (p.right == null || p.right == prev) {
                res.add(p.val);
                prev = p;
                p = null;
            } else {
                stk.push(p);
                p = p.right;
            }

        }
        return res;
    }

}