Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
    stack1.push(node);
}

public int pop() {
    if(stack2.isEmpty()){
        while (!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}

private Stack<Integer> stack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();

public void push(int node) {
    stack.push(node);
    if(minStack.isEmpty() || node<minStack.peek()){ 
        //注意：minStack 一开始栈为空,则直接如 minStack 栈
        minStack.push(node);
    }
}

public void pop() {
    if(stack.peek()==minStack.peek()){
        minStack.pop();
    }
    stack.pop();
}

public int top() {
    return stack.peek();
}

public int min() {
    return minStack.peek();
}

public boolean IsPopOrder(int [] pushA,int [] popA) {
    int n = pushA.length;

    //使用一个栈来模拟弹出、压出操作。
    Stack<Integer> stack=new Stack<>();

    for(int pushIndex=0,popIndex=0;pushIndex<n;pushIndex++){
        stack.push(pushA[pushIndex]);
        while(popIndex<n && stack.peek()==popA[popIndex]){
            stack.pop();
            popIndex++;
        }
    }
    return stack.isEmpty();
}

public boolean isValid(String s) {
    if(s.length()==0){
        return true;
    }
    Stack<Character> stack=new Stack<>();
    for(int i=0;i<s.length();i++){
        char c=s.charAt(i);
        if(c=='(' || c=='[' || c=='{'){
            stack.push(c);
        }else{ // c 可能的取值是 ')' ']' ,'}'
            if(stack.isEmpty()){ //没有左括号进栈式不对的
                return false;
            }
            char validChar=' ';
            char topChar=stack.peek();
            if(topChar=='('){
                validChar=')';
            }else if(topChar=='['){
                validChar=']';
            }else if(topChar=='{'){
                validChar='}';
            }
            if(c==validChar){
                stack.pop();
            }else{
                return false;
            }
        }
    }
    return stack.isEmpty();
}

//GO 表示访问节点，PRINT 表示打印节点
private enum Command{GO,PRINT};

private class StackNode{
    TreeNode node;
    Command command;
    public StackNode(TreeNode node,Command command){
        this.node=node;
        this.command=command;
    }
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res=new ArrayList<>();
    if(root==null){
        return res;
    }

    Stack<StackNode> stack=new Stack<>();
    stack.push(new StackNode(root,Command.GO));

    //前序遍历，利用栈模拟递归方式
    while(!stack.isEmpty()){
        StackNode stackNode=stack.pop();
        TreeNode treeNode=stackNode.node;
        Command command=stackNode.command;
        if(command.equals(Command.PRINT)){
            res.add(treeNode.val);
        }else{ // Command.GO 继续访问
            if(treeNode.right!=null){
                stack.push(new StackNode(treeNode.right,Command.GO));
            }
            if(treeNode.left!=null){
                stack.push(new StackNode(treeNode.left,Command.GO));
            }
            stack.push(new StackNode(treeNode,Command.PRINT));
        }
    }
    return res;
}

private enum Command{GO,PRINT};

private class StackNode{
    TreeNode node;
    Command command;
    public StackNode(TreeNode node,Command command){
        this.node=node;
        this.command=command;
    }
}

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res=new ArrayList<>();
    if(root==null){
        return res;
    }
    Stack<StackNode> stack=new Stack<>();
    stack.push(new StackNode(root,Command.GO));

    while(!stack.isEmpty()){
        StackNode stackNode=stack.pop();
        TreeNode treeNode=stackNode.node;
        Command command=stackNode.command;
        if(command.equals(Command.PRINT)){
            res.add(treeNode.val);
        }else{
            if(treeNode.right!=null){
                stack.push(new StackNode(treeNode.right,Command.GO));
            }
            stack.push(new StackNode(treeNode,Command.PRINT));
            if(treeNode.left!=null){
                stack.push(new StackNode(treeNode.left,Command.GO));
            }
        }
    }
    return res;
}

private enum Command{GO,PRINT};

private class StackNode{
    TreeNode node;
    Command command;
    public StackNode(TreeNode node,Command command){
        this.node=node;
        this.command=command;
    }
}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res=new ArrayList<>();
    if(root==null){
        return res;
    }

    Stack<StackNode> stack=new Stack<>();
    stack.push(new StackNode(root,Command.GO));

    while(!stack.isEmpty()){
        StackNode stackNode=stack.pop();
        TreeNode treeNode=stackNode.node;
        Command command=stackNode.command;
        if(command.equals(Command.PRINT)){
            res.add(treeNode.val);
        }else{
            stack.push(new StackNode(treeNode,Command.PRINT));
            if(treeNode.right!=null){
                stack.push(new StackNode(treeNode.right,Command.GO));
            }
            if(treeNode.left!=null){
                stack.push(new StackNode(treeNode.left,Command.GO));
            }
        }
    }
    return res;
}