题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

分析
用两个栈来实现，先把根结点放入s1，当行数为偶数时，s2从左到右放结点；当行数为奇数时，s1从右到左放结点；

笔者用java写的程序不能100%AC，但c++却可以，有大神可以指出来哪里有问题吗？

代码一
import java.util.ArrayList;
import java.util.Stack;

public class ZhiZiPrint {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                TreeNode node1 = new TreeNode(1);
                TreeNode node2 = new TreeNode(2);
                TreeNode node3 = new TreeNode(3);
                TreeNode node4 = new TreeNode(4);
                TreeNode node5 = new TreeNode(5);
                TreeNode node6 = new TreeNode(6);
                TreeNode node7 = new TreeNode(7);
                TreeNode node8 = new TreeNode(8);
                node1.left = node3;
                node1.right = node2;
                node3.left = node4;
                node3.right = node5;
                node2.left = node6;
                node2.right = node7;
                node7.left = node8;
                ZhiZiPrint test = new ZhiZiPrint();
                ArrayList<ArrayList<Integer> > lists = test.Print(node1);
                for(ArrayList<Integer> list: lists){
                        for(int num: list){
                                System.out.println(num);
                        }
                }
        }
       
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            if(pRoot == null){
                    return null;
            }
            ArrayList<ArrayList<Integer> > lists = fun(pRoot);
            return lists;
    }

    public ArrayList<ArrayList<Integer>> fun(TreeNode root){
            ArrayList<ArrayList<Integer> > lists = new ArrayList<>();
             Stack<TreeNode> s1 = new Stack<>();
            Stack<TreeNode> s2 = new Stack<>();
            s1.push(root);
            while(!s1.isEmpty() || !s2.isEmpty()){
                if(!s1.isEmpty()){
                        ArrayList<Integer> list = new ArrayList<>();
                        int len1 = s1.size();
                        for(int i=0; i<len1; i++){
                                TreeNode node = s1.peek();
                            list.add(node.val);
                            s1.pop();
                            if(node.left != null){
                                    s2.push(node.left);
                            }
                            if(node.right != null){
                                    s2.push(node.right);
                            }
                        }

                    lists.add(list);
                }
                if(!s2.isEmpty()){
                        ArrayList<Integer> list = new ArrayList<>();
                        int len2 = s2.size();
                        for(int i=0; i<len2; i++){
                                TreeNode node = s2.pop();
                            list.add(node.val);
                            if(node.right != null){
                                    s1.push(node.right);
                            }
                            if(node.left != null){
                                    s1.push(node.left);
                            }
                        }

                    lists.add(list);
                }
               
            }

            return lists;
    }

}
代码二（来源于牛客网）
链接：https://www.nowcoder.com/questio ... e8097390d107d2efbe0
来源：牛客网

//思路2：利用两个栈分别存储奇数行和偶数行
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if(!pRoot)return res;
        stack<TreeNode*> sta1;    //建立两个栈，栈1用于存放奇数行节点，栈2用于存放偶数行节点
        stack<TreeNode*> sta2;
        sta1.push(pRoot);
        vector<int> vec;    //行容器，用于存入当前行输出的结果
        while(!sta1.empty()||!sta2.empty()){
          if(sta2.empty()&&!sta1.empty()){
               int len_1=sta1.size();
             for(int i=0;i<len_1;i++){
                TreeNode* tmp=sta1.top();
                vec.push_back(tmp->val);
                sta1.pop();
                if(tmp->left)sta2.push(tmp->left);    //栈2存放偶数行节点，按照从左子节点到右子节点的顺序push
                if(tmp->right)sta2.push(tmp->right);
             }
               res.push_back(vec);
               vec.clear();
          }

          if(sta1.empty()&&!sta2.empty()){
                int len_2=sta2.size();
             for(int i=0;i<len_2;i++){
                TreeNode* tmp=sta2.top();
                vec.push_back(tmp->val);
                sta2.pop();
                if(tmp->right)sta1.push(tmp->right);    //栈1存放奇数行节点，按照从右子节点到左子节点的顺序push
                if(tmp->left)sta1.push(tmp->left);
            }
              res.push_back(vec);
               vec.clear();
         }
        }
        return res;
    }
};

---------------------
作者：另一个我竟然存在
来源：CSDN
原文：https://blog.csdn.net/qq_24034545/article/details/84376872
版权声明：本文为博主原创文章，转载请附上博文链接！

奈斯