数据结构与算法——Java实现 28.二叉树的锯齿形层序遍历
努力成为你想要成为的那种人，去奔赴你想要的生活
—— 24.10.4
103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
思路——双端队列实现
每一层的队列添加顺序不一样，根据层数进行判断，如果是奇数层从左到右遍历，从队列尾部添加，如果是偶数层，从右向左遍历，从队列首部添加，定义每一层的节点数和每一层的层数，进行迭代
LinkedListQueue
import java.util.Iterator;// 用泛型好处：1.用null代表特殊值 2.代表更多类型
public class LinkedListQueue<E>implements Queue<E>,Iterable<E> {// 静态内部结点类private static class Node<E>{E value;Node<E> next;public Node(E value, Node<E> next){this.value = value;this.next = next;}}// 定义队列的头结点和尾节点Node<E> head = new Node<>(null,null);Node<E> tail = head;private int size = 0; // 节点数private int capacity = 10; // 容量public LinkedListQueue(int capacity) {this.capacity = capacity;tail.next = head;}public LinkedListQueue() {tail.next = head;}/*队列插入方法，在尾部插入Params:value-待插入值Returns：插入成功返回true，插入失败返回false*/@Overridepublic boolean offer(E e) {if(isFull()){return false;}Node<E> newNode = new Node<>(e,head);tail.next = newNode;tail = newNode;size++;return true;}/*从队头获取值，并移除Returns：如果队列非空返回队头值，否则返回null*/@Overridepublic E poll() {if (isEmpty()){return null;}Node<E> first = head.next;head.next = first.next;if (first == tail){tail = head;}size--;return first.value;}/*从队列头获取值，不移除Returns：如果队列非空返回队头值，否则返回null*/@Overridepublic E peek() {if(isEmpty()){return null;}return head.next.value;}/*检查队列是否为空Return：空返回true，否则返回false*/@Overridepublic boolean isEmpty() {return head == tail;}/*检查队列是否为满Return：满返回true，否则返回false*/@Overridepublic boolean isFull() {return size == capacity;}// 队列遍历方法 迭代器@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> current = head.next;@Overridepublic boolean hasNext() {return current != head;}@Overridepublic E next() {E value = current.value;current = current.next;return value;}};}
}
TreeNode
public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.left = left;this.val = val;this.right = right;}@Overridepublic String toString() {return String.valueOf(this.val);}
}
锯齿形层序遍历
import Day10Queue.LinkedListQueue;
import Day10Queue.TreeNode;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class LeetCode103ZiazagForEach {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();queue.offer(root);int c1 = 1; // 当前层节点数boolean odd = true; // 奇数层while (!queue.isEmpty()) {LinkedList<Integer> level = new LinkedList<>(); // 保存每一层的结果int c2= 0; // 下一层节点数for (int i = 0; i < c1; i++) {TreeNode n = queue.poll();if (odd){level.offerLast(n.val);}else{level.offerFirst(n.val);}if (n.left != null) {queue.offer(n.left);c2++;}if (n.right != null) {queue.offer(n.right);c2++;}}odd = !odd;res.add(level);c1 = c2;}return res;}public static void main(String[] args) {/*1/ \2 5/ \ / \3 4 6 7*/TreeNode root = new TreeNode(1,new TreeNode(2,new TreeNode(3),new TreeNode(4)),new TreeNode(5,new TreeNode(6),new TreeNode(7)));List<List<Integer>> lists = new LeetCode103ZiazagForEach().zigzagLevelOrder(root);for (List<Integer> list : lists) {System.out.println(list);}}}
力扣题解
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new LinkedList<List<Integer>>();if (root == null) {return ans;}Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();nodeQueue.offer(root);boolean isOrderLeft = true;while (!nodeQueue.isEmpty()) {Deque<Integer> levelList = new LinkedList<Integer>();int size = nodeQueue.size();for (int i = 0; i < size; ++i) {TreeNode curNode = nodeQueue.poll();if (isOrderLeft) {levelList.offerLast(curNode.val);} else {levelList.offerFirst(curNode.val);}if (curNode.left != null) {nodeQueue.offer(curNode.left);}if (curNode.right != null) {nodeQueue.offer(curNode.right);}}ans.add(new LinkedList<Integer>(levelList));isOrderLeft = !isOrderLeft;}return ans;}
}
