32.3 按之字形顺序打印二叉树

Leetcode

题目描述

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

解题思路

在 32.2 按层输出的基础上，用 reverse 标记当前层的方向：第 1 层从左到右，第 2 层把这一层的 list 翻转后再加入结果，之后每层交替。

public List<List<Integer>> decorateRecord(TreeNode root) {
    List<List<Integer>> ret = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    boolean reverse = false;
    while (!queue.isEmpty()) {
        List<Integer> list = new ArrayList<>();
        int cnt = queue.size();
        while (cnt-- > 0) {
            TreeNode node = queue.poll();
            if (node == null)
                continue;
            list.add(node.val);
            queue.add(node.left);
            queue.add(node.right);
        }
        if (reverse)
            Collections.reverse(list);
        reverse = !reverse;
        if (list.size() != 0)
            ret.add(list);
    }
    return ret;
}