数据结构算法（二叉树的锯齿形层次遍历）

目录

71. 二叉树的锯齿形层次遍历

给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）

样例 1：

输入:{1,2,3}
输出:[[1],[3,2]]
解释:
1
/ \
2 3
它将被序列化为 {1,2,3}

样例 2：

输入:{3,9,20,#,#,15,7}
输出:[[3],[20,9],[15,7]]
解释:
3
/ \
9 20
   / \
15 7
它将被序列化为 {3,9,20,#,#,15,7}

import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; import java.util.List; /**
 * Definition of TreeNode:
 * public class TreeNode {
 * public int val;
 * public TreeNode left, right;
 * public TreeNode(int val) {
 * this.val = val;
 * this.left = this.right = null;
 * }
 * }
 */ public class Solution { /**
	 * @param root: A Tree
	 * @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
	 */ public List<List<Integer>> zigzagLevelOrder(TreeNode root) { // write your code here if (root == null) { return new ArrayList<>(); } List<List<Integer>> ret = new ArrayList<>(); Deque<TreeNode> q = new LinkedList<>(); q.addLast(root); int level = 0; while (!q.isEmpty()) { List<Integer> levelRet = new ArrayList<>(); int size = q.size(); level++; while (--size >= 0) { if (level % 2 == 1) { TreeNode node = q.pollFirst(); levelRet.add(node.val); if (node.left != null) { q.addLast(node.left); } if (node.right != null) { q.addLast(node.right); } } else { TreeNode node = q.pollLast(); levelRet.add(node.val); if (node.right != null) { q.addFirst(node.right); } if (node.left != null) { q.addFirst(node.left); } } } ret.add(levelRet); } return ret; } } 

原题链接点这里

本文地址：https://blog.csdn.net/leyi520/article/details/108034428