LeetCode:103. 二叉树的锯齿形层序遍历

目次
标题形貌:
代码:

---

这个与二叉树的层序遍历有点类似
标题形貌:

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

1. <strong>输入：</strong>root = [3,9,20,null,null,15,7]
2. <strong>输出：</strong>[[3],[20,9],[15,7]]

复制代码

示例 2：

1. <strong>输入：</strong>root = [1]
2. <strong>输出：</strong>[[1]]

复制代码

示例 3：

1. <strong>输入：</strong>root = []
2. <strong>输出：</strong>[]

复制代码

代码:

1.    public List<List<Integer>> zigzaLevelOrder(TreeNode root) {
2.         List<List<Integer>> res = new ArrayList<>();
3.         if (root == null) return res;
4.         LinkedListQueue<TreeNode> queue = new LinkedListQueue<TreeNode>();//单向环形哨兵链表
5.         queue.offer(root);
6.         int c1 = 1;//当前的节点数
7.         boolean odd = true;//奇数层
8.         while (!queue.isEmpty()) {
9.             LinkedList<Integer> level = new LinkedList<>();//每一层的节点  jdk自带的
10.             int c2 = 0;
11.             for (int i = 0; i < c1; i++) {
12.                 TreeNode n = queue.poll();
13.                if(odd){  //奇数层从左到右
14.                    level.offerLast(n.val);//尾部插入
15.                }else{//偶数层从右到左
16.                    level.offerFirst(n.val);//头部插入
17.                }
18.                 if (n.left != null) {
19.                     queue.offer(n.left);
20.                     c2++;
21.                 }
22.                 if (n.right != null) {
23.                     queue.offer(n.right);
24.                     c2++;
25.                 }
26.             }
27.             odd = !odd;//取反
28.             res.add(level);
29.             c1 = c2;
31.         }
32.         return res;
33.     }

复制代码