import java.util.ArrayDeque;

public class NonRecuDfs {
    public static ArrayDeque<TreeNode> preArr = new ArrayDeque<>();
    public static ArrayDeque<TreeNode> inArr = new ArrayDeque<>();
    public static ArrayDeque<TreeNode> afterArr = new ArrayDeque<>();

    public static void preOrder(TreeNode root){
        while(!preArr.isEmpty() || root!=null){
            if(root!=null){
                System.out.print(root.val+" ");
                preArr.push(root);
                root = root.left;
            }else{
                TreeNode t = preArr.pop();
                root = t.right;
            }
        }
    }
    public static void inOrder(TreeNode root){
        while(!inArr.isEmpty() || root!=null){
            if(root!=null){
                inArr.push(root);
                root = root.left;
            }else{
                TreeNode t = inArr.pop();
                System.out.print(t.val+" ");
                root = t.right;
            }
        }
    }
    public static void afterOrder(TreeNode root){
        TreeNode pre = null;
        while(!afterArr.isEmpty() || root!=null){
            while(root!=null){
                afterArr.push(root);
                root = root.left;
            }
            root = afterArr.pop();//通过栈可以确定，当前出栈元素的左子树都已经访问过了，剩下右子树需要靠pre来确定是否访问过
            if(root.right==null || root.right==pre){
                //右子树为空或者已被访问
                System.out.print(root.val+" ");
                pre = root;
                root = null;//设为空避免下次的while循环
            }else {
                afterArr.push(root);
                root = root.right;
            }
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(3);
        TreeNode treeNode3 = new TreeNode(4);
        TreeNode treeNode4 = new TreeNode(5);
        TreeNode treeNode5 = new TreeNode(6);
        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        treeNode1.left = treeNode3;
        treeNode1.right = treeNode4;
        treeNode2.left = treeNode5;
        preOrder(treeNode);
        System.out.println();
        inOrder(treeNode);
        System.out.println();
        afterOrder(treeNode);

    }
}
class TreeNode {
      int val;
      TreeNode left = null;
      TreeNode right = null;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}