题解 | 按之字形顺序打印二叉树

两层循环竟然能过。

直接层序遍历，每层换一次方向。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        // write code here
        // 1.层序遍历
        // 2.每层遍历时要换方向，先尾插，再头插
        // 1 | 3 2 | 4 5

        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

        if (pRoot == null) return res;

        q.add(pRoot);
        int direction = 1;  // 方向计数器
        while (!q.isEmpty()) {
            ArrayList<Integer> layer = new ArrayList<>();
            int layerLen = q.size();

            for (int i = 0; i < layerLen; i++) {
                TreeNode node = q.poll();
                if (direction % 2 != 0) layer.add(node.val);
                else layer.add(0, node.val);

                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            res.add(layer);
            direction++;
        }


        return res;
    }
}