请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果:
[
[3],
[20,9],
[15,7]
]
提示:
节点总数 <= 1000 分析:
方法:BFS+标识
实现方式和 II. 从上到下打印二叉树 II 一样,不同之处在于每层的元素顺序的是反过来的,可以定义一个标识来记录左右,一层遍历完就把该标识赋为另一个方向。反向遍历的方式有很多种,比如每次插入在 List 集合的首位,从双队列的头部插入等等,我这里采用的第一种。
时间复杂度:O(n)
空间复杂度:O(n)
class Solution { public List> levelOrder(TreeNode root) { //判断空树 if(root == null){ return new ArrayList(); } //定义队列 Deque
queue = new ArrayDeque<>(); //入栈 queue.offerLast(root); //创建List集合存储每层的List集合 List > res = new ArrayList<>(); //标识左右打印 boolean flag = true; //遍历 while(!queue.isEmpty()){ //获取队列长度 int size = queue.size(); //定义List集合存储该层的节点值 List
list = new ArrayList<>(); //按层次遍历 while(size-- > 0){ //出栈 TreeNode node = queue.pollFirst(); //添加节点值 //从左到右 if(flag){ list.add(node.val); } //从右到左 else{ list.add(0, node.val); } //左节点不为空添加左节点 if(node.left != null){ queue.offerLast(node.left); } //右节点不为空添加右节点 if(node.right != null){ queue.offerLast(node.right); } } //改变打印方向 flag = !flag; //将List集合添加到List集合中 res.add(list); } return res; } }
题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)