面试算法-48-二叉树的锯齿形层序遍历

题目

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

解

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<TreeNode> queue2 = new LinkedList<>();
        queue.offer(root);
        boolean flag = true;
        LinkedList<Integer> res = new LinkedList<>();
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (flag) {
                res.add(poll.val);
            } else {
                res.addFirst(poll.val);
            }
            if (poll.left != null) {
                queue2.offer(poll.left);
            }
            if (poll.right != null) {
                queue2.offer(poll.right);
            }
            if (queue.isEmpty()) {
                flag = !flag;
                result.add(res);
                res = new LinkedList<>();
                queue = queue2;
                queue2 = new LinkedList<>();
            }

        }
        return result;
    }
}