leetcode 103 Solution

代码解析

package com.demo.s103;

import java.util.*;

/**
 * 二叉树的锯齿形层序遍历
 * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //定义返回结果集
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        //定义队列
        Queue<TreeNode> queue = new LinkedList();
        //放入根节点
        queue.offer(root);
        //定义顺序
        boolean zig = true;
        //从队列取值
        while(queue.size() != 0) {
            int size = queue.size();
            //每层单独存放到对应的链表中，头插尾插 根据zig区分
            Deque<Integer> level = new LinkedList();
            for(int i = 0 ;i < size; i ++) {
                //队列取值
                TreeNode cur = queue.poll();
                if(zig) {
                    level.offerLast(cur.val);
                } else {
                    level.offerFirst(cur.val);
                }
                //当前节点不为null，取下一层，从左往右
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }

            }
            //每下层更新下 zig
            zig = !zig;
            ret.add(new LinkedList(level));

        }
        return ret;
    }
}