按之字形顺序打印二叉树-使用两个栈BFS（O(n),O(n)）

//解题思路
/*
BFS（O(n),O(n)）：
需要使用两个栈（打印层和待打印层要放在独立的两个栈里）
       8
    6    10
   5 7  9  11
具体可看代码注释，同时使用以上二叉树进行演算即可明白
 */
//popStack；打印节点栈
//saveStack:保存待打印层节点栈
//direction：打印方向，true为正向（使用saveStack保存待打印层节点时要先添加左孩子，再添加右孩子），false为反向（要先添加右孩子，再添加左孩子）
private ArrayList<Integer> print(Stack<TreeNode> popStack,Stack<TreeNode> saveStack,boolean direction) {
    ArrayList<Integer> result = new ArrayList<>();
    while (!popStack.isEmpty()){
        TreeNode treeNode = popStack.pop();
        result.add(treeNode.val);
        if (direction){
            if (treeNode.left != null) saveStack.add(treeNode.left);
            if (treeNode.right != null) saveStack.add(treeNode.right);
        }else {
            if (treeNode.right != null) saveStack.add(treeNode.right);
            if (treeNode.left != null) saveStack.add(treeNode.left);
        }
    }
    return result;
}
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    if (pRoot == null) return new ArrayList<>();
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    Stack<TreeNode> stack1 = new Stack<>();//存正向打印的节点
    Stack<TreeNode> stack2 = new Stack<>();//存反向打印的节点
    stack1.add(pRoot);
    while (!stack1.isEmpty() || !stack2.isEmpty()){
        //stack1为空，则stack2为打印节点栈，stack1为保存待打印层节点栈，此时反向打印(false)
        //反之则stack1为打印节点栈，stack2为保存待打印层节点栈,此时正向打印(true)
        result.add(stack1.isEmpty() ? print(stack2,stack1,false) : print(stack1,stack2,true));
    }
    return result;
}