面试题32：从上到下打印二叉树（不分层，分层，之字形）

不分层：

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            TreeNode treeNode = queue.poll();
            result.add(treeNode.val);
            if (treeNode.left != null) queue.offer(treeNode.left);
            if (treeNode.right != null) queue.offer(treeNode.right);
        }

        return result;
    }

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。（分层）

思路一：利用队列，层次遍历的方式，存入list

// 也是分行打印，比上面简洁
    public void printEveryLayer(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int layerSize = queue.size();
            for (int i = 0; i < layerSize; i++) {
                TreeNode node = queue.poll();
                System.out.println(node.val+" ");
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            System.out.println();
        }
    }

    /**
     * 统计队列中每一层的节点数，循环添加
     * @param pRoot
     * @return
     */
    ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);

        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (pRoot == null) return lists;
        ArrayList<Integer> layerList = new ArrayList<>();
        while (!queue.isEmpty()){
            int layerSize = queue.size();
            //每次都将每一行统计完再出循环，进入下一行
            for (int i=0;i<layerSize;++i){
                TreeNode temp = queue.poll();
                layerList.add(temp.val);

                if (temp.left != null) queue.offer(temp.left);
                if (temp.right != null) queue.offer(temp.right);

            }
            lists.add(new ArrayList<Integer>(layerList));
            layerList.clear();
        }
        return lists;
    }

思路二：
递归构造一个参数为根节点，当前深度，和list的节点。递归左右节点，每次深度加1

/**
     * 递归解法
     * @param pRoot
     * @return
     */
    ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        depth(pRoot,1,lists);
        return lists;
    }

    private void depth(TreeNode treeNode, int depth, ArrayList<ArrayList<Integer>> lists) {
        if (treeNode == null) return;
        //深度改变时，才往集合中加入新的list
        if (depth > lists.size()){
            lists.add(new ArrayList<Integer>());
        }
        //直接将该节点值接如最后的list中
        lists.get(depth-1).add(treeNode.val);

        depth(treeNode.left,depth+1,lists);
        depth(treeNode.right,depth+1,lists);
    }

思路三：设置两个变量，记录层次和每层的数量。

/**
     * 思路，增加两个变量分别表示当前行的节点数目和下一行的节点数目
     * 每打印一次当前行减一，每添加一次子节点下一行加1
     * 当前行为0时赋值下一行，下一行清0
     * @param pRoot
     * @return
     */
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        int toBePrinted = 1;
        int nextLevel = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        if (pRoot == null) return list;
        //放在循坏里会变成每次只有一个
        ArrayList<Integer> perList = new ArrayList<>();
        while (!queue.isEmpty()){

            TreeNode temp = queue.poll();
            perList.add(temp.val);
            toBePrinted--;


            if (temp.left != null){
                queue.offer(temp.left);
                nextLevel++;
            }
            if (temp.right != null){
                queue.offer(temp.right);
                nextLevel++;
            }

            if (toBePrinted == 0){
                list.add(new ArrayList<Integer>(perList));
                //直接把内存地址清空
                perList.clear();
                /**
                 * 或者采用如下注释
                 *
                 */
//                list.add(perList);
//                perList = new ArrayList<Integer>();
                toBePrinted = nextLevel;
                nextLevel = 0;
            }
        }

        return list;
    }

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
用两个栈去分奇偶行记录下一行，主要体现在出栈存储下一行的区别上
当前奇数行，下一行偶数行要从右向左打印，先记录左节点，右节点先出。
当前偶数行，下一行奇数行从左向右打印，先记录右节点，左节点先出。

public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

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

        }

    }

    /**
     * 两个栈记录不同方向的输出，一个记录奇数行从左到右，一个记录偶数行从右到左，循环打印
     * 打印后一行后，改变左右节点的放入顺序，先进先出
     * @param pRoot
     * @return
     */
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
           ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
           if (pRoot == null) return  lists;

           LinkedList<TreeNode> stackOdd = new LinkedList<>();
           LinkedList<TreeNode> stackEven = new LinkedList<>();
           stackOdd.push(pRoot);

           //有一个不为空，则循环继续
           while (!stackOdd.isEmpty() || !stackEven.isEmpty()){
               ArrayList<Integer> perList = new ArrayList<>();
               if (!stackOdd.isEmpty()){
                   while (!stackOdd.isEmpty()){
                       TreeNode temp = stackOdd.pop();
                       perList.add(temp.val);

                       if (temp.left != null) stackEven.push(temp.left);
                       if (temp.right != null) stackEven.push(temp.right);
                   }
               }else {
                   while (!stackEven.isEmpty()){
                       TreeNode temp = stackEven.pop();
                       perList.add(temp.val);

                       if (temp.right != null) stackOdd.push(temp.right);
                       if (temp.left != null) stackOdd.push(temp.left);
                   }
               }
               lists.add(perList);
           }
          return lists;
    }