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

import java.util.ArrayList;
import java.util.LinkedList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        LinkedList<TreeNode> nodes = new LinkedList<>();
        ArrayList <ArrayList<Integer>>results = new ArrayList();
        boolean reverse = true;
        if (pRoot != null) {
            nodes.add(pRoot);
            while (!nodes.isEmpty()) {
                ArrayList<Integer> integers = new ArrayList();
                int size = nodes.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = nodes.poll();
                    if (reverse) {
                        integers.add(node.val);
                    } else {
                        integers.add(0, node.val);
                    }
                    if (node.left != null) {
                        nodes.offer(node.left);
                    }
                    if (node.right != null) {
                        nodes.offer(node.right);
                    }
                }
                if (integers.size() != 0) {
                    results.add(integers);
                }
                reverse = !reverse;
            }
        }
        return results;
    }

}

解题思想：

1. 借助双向链表，初始化⼀个添加⽅向 boolean 值，先将根节点添加进去：

2. 获取 list ⾥⾯剩下的元素的个数，挨个取出就是⼀层，取出的时候，如果reverse 为 true ，则往链表的第 0 个索引位置添加，否则直接在后⾯添加，然后判断每⼀个取出来的节点的左右节点是不是为空，不为空则加⼊链表。

3. 每⼀层处理完之后，将 list 加⼊结果集中，然后翻转 reverse 的值，继续判断list 是不是为空，执⾏第⼆步循环。