【Java - L - 0103】m - 二叉树的锯齿形层序遍历

题目描述

lc

实现

32】之字形打印二叉树

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/// 1 1// / \// 2 3 3,2/// \ \//4 5 6 4,5,6 先进后出 奇数 入队头 6 5 4// / \// 7 8 8,7 先进先出 偶数 入队尾 7 8class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();if (root == null) return res;boolean flag = true;//从左向右打印为true，从右向左打印为falseDeque<TreeNode> deque = new LinkedList<>();deque.offerLast(root);while (!deque.isEmpty()) {
    int len = deque.size(); //每一层的长度List<Integer> list = new ArrayList<>();TreeNode node;while (len > 0) {
    // 偶，先进先出 队尾 奇，先进后出(栈) 队头if (flag) {
    // 前取后放：从左向右打印，所以从前边取，后边放入node = deque.pollFirst(); // 1if (node.left != null) // (1)| 2 3 (4) (5) 6|(7) (8)deque.offerLast(node.left);if (node.right != null)deque.offerLast(node.right);} else {
    //后取前放： 从右向左，从后边取，前边放入node = deque.pollLast();  //4 5 (6) | 2 (3)if (node.right != null)deque.offerFirst(node.right);if (node.left != null)deque.offerFirst(node.left);}list.add(node.val);len--;}flag = !flag;res.add(list);}return res;}}