二叉树算法之【Z字型层序遍历】

目录

LeetCode-103题

LeetCode-103题

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

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();// checkif (root == null)return result;// 借助队列来实现Queue<TreeNode> queue = new LinkedList<>();// 先将根节点放到队列中queue.offer(root);// 用于记录当前层的节点数量int c1 = 1;// 用于标识添加方向int flag = 1;// 只要队列不为空while (!queue.isEmpty()) {// 用于记录下一层节点数量int c2 = 0;LinkedList<Integer> inner = new LinkedList<>();for (int i = 0; i < c1; i++) {TreeNode curr = queue.poll();// 根据标识判断addLast还是addFirstif (flag % 2 == 1) {inner.addLast(curr.val);} else {inner.addFirst(curr.val);}// 有左子节点if (curr.left != null) {// 将左子节点添加到队列中queue.offer(curr.left);// 记录下一层节点数量标识+1c2++;}// 有右子节点if (curr.right != null) {// 将右子节点添加到队列中queue.offer(curr.right);// 记录下一层节点数量标识+1c2++;}}// 下一轮遍历通过c1就知道当前层有多少个节点了c1 = c2;// 下一层换个方向，以达到Z字形flag++;result.add(inner);}return result;}
}