[数据结构与算法]剑指Offer - 32-3_从上到下打印二叉树

题目描述

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

示例

输入：
	3
   / \
  9  20
    /  \
   15   7
输出：
[
  [3],
  [20,9],
  [15,7]
]

思路

1. 采用广度优先搜索，从头结点开始遍历，先把头结点添加进队列
2. 然后从队列取结点，取的数量为当前队列的大小，这些刚好都是同一层的节点
3. 然后依次把值添加进对应层的结果集中，然后判断当前节点有没有左右结点，如果有，依次添加进队列，然后把当前层的结果集添加进整体结果集中
4. 在添加之前，如果整体结果集大小是奇数，则表示当前是树的偶数层，那么反转当前层的结果
5. 以此类推，遍历队列，最后得到结果

Code

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (null == root) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (null != node.left) {
                    queue.add(node.left);
                }
                if (null != node.right) {
                    queue.add(node.right);
                }
            }
            //反转
            if (result.size() % 2 == 1) {
                Collections.reverse(list);
            }
            result.add(list);
        }
        return result;
    }
}