一刷327剑指Offer32III.从上到下打印二叉树III（m）

题目&＃xff1a;
请实现一个函数按照之字形顺序打印二叉树&＃xff0c;
即第一行按照从左到右的顺序打印&＃xff0c;第二层按照从右到左的顺序打印&＃xff0c;第三行再按照从左到右的顺序打印&＃xff0c;
其他行以此类推。
--------------------------
示例:
给定二叉树: [3,9,20,null,null,15,7],3/ \9 20/ \15 7
返回其层次遍历结果&＃xff1a;
[[3],[20,9],[15,7]
]
提示&＃xff1a;
节点总数 <&＃61; 1000
----------------


思考&＃xff1a;层序遍历 &＃43; 双端队列&＃xff08;Java 中将链表 LinkedList 作为双端队列使用。&＃xff09;
利用双端队列的两端皆可添加元素的特性&＃xff0c;设打印列表&＃xff08;双端队列&＃xff09; tmp &＃xff0c;并规定&＃xff1a;
奇数层 则添加至 tmp 尾部 &＃xff0c;
偶数层 则添加至 tmp 头部 。
------------------
算法流程&＃xff1a;
1、特例处理&＃xff1a; 当树的根节点为空&＃xff0c;则直接返回空列表 [] &＃xff1b;
2、初始化&＃xff1a; 打印结果空列表 res &＃xff0c;包含根节点的双端队列 deque &＃xff1b;
3、BFS 循环&＃xff1a; 当 deque 为空时跳出&＃xff1b;1、新建列表 tmp &＃xff0c;用于临时存储当前层打印结果&＃xff1b;2、当前层打印循环&＃xff1a; 循环次数为当前层节点数&＃xff08;即 deque 长度&＃xff09;&＃xff1b;1、出队&＃xff1a; 队首元素出队&＃xff0c;记为 node&＃xff1b;2、打印&＃xff1a; 若为奇数层&＃xff0c;将 node.val 添加至 tmp 尾部&＃xff1b;否则&＃xff0c;添加至 tmp 头部&＃xff1b;3、添加子节点&＃xff1a; 若 node 的左&＃xff08;右&＃xff09;子节点不为空&＃xff0c;则加入 deque &＃xff1b;3、将当前层结果 tmp 转化为 list 并添加入 res &＃xff1b;
4、返回值&＃xff1a; 返回打印结果列表 res 即可&＃xff1b;
----------------
复杂度分析&＃xff1a;
时间复杂度 O(N)&＃xff1a; N 为二叉树的节点数量&＃xff0c;即 BFS 需循环 N 次&＃xff0c;占用 O(N)&＃xff1b;双端队列的队首和队尾的添加和删除操作的时间复杂度均为 O(1) 。
空间复杂度 O(N)&＃xff1a; 最差情况下&＃xff0c;即当树为满二叉树时&＃xff0c;最多有 N/2 个树节点 同时 在 deque 中&＃xff0c;使用 O(N)大小的额外空间。
------------------
Java 中将链表 LinkedList 作为双端队列使用。
------------------
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue &＃61; new LinkedList<>();//定义双端队列List<List<Integer>> res &＃61; new ArrayList<>();//定义结果集&＃xff1a; 动态数组if (root &＃61;&＃61; null) return res;//特判queue.add(root);//双端队列初始化while (!queue.isEmpty()) {//循环结束条件LinkedList<Integer> temp &＃61; new LinkedList<>();for (int i &＃61; queue.size(); i > 0; i--) {TreeNode node &＃61; queue.poll();if (res.size() % 2 &＃61;&＃61; 0) {temp.addLast(node.val);//偶数层-> 队列头部 temp}else temp.addFirst(node.val);//奇数层-> 队列尾部 tempif (node.left !&＃61; null) queue.add(node.left);if (node.right !&＃61; null) queue.add(node.right);}res.add(temp);}return res;}
}


LC