103. 二叉树的锯齿形层序遍历
16lz
2021-03-10
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
解题思路:使用层次遍历,将LinkedList当做双向链表使用。
class Solution { //LinkeList双向链表,add插入到尾部,,push插入到头部 public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null ) return res; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); int level = 0; while(!queue.isEmpty()){ int size = queue.size(); LinkedList<Integer> temp = new LinkedList<Integer>(); for(int i = 0; i < size; i++){ root = queue.poll(); if((level&1) == 1) //如果是奇数层,就push插入到双向链表的头部 temp.push(root.val); else{ //如果是偶数层,就add插入到双向链表尾部 temp.add(root.val); } if(root.left != null){ queue.add(root.left); } if(root.right != null){ queue.add(root.right); } } // if((level&1) == 1){ // Collections.reverse(temp); // } res.add(temp); level++; } return res; }}
©著作权归作者所有:来自51CTO博客作者wx5d3c7e0ad6c30的原创作品,如需转载,请注明出处,否则将追究法律责任
更多相关文章
- 从数组中移除元素,要求时间复杂度为O(N)空间复杂度为O(1)
- 2021-02-26:一个数组arr是二叉树的中序遍历结果,每条边的开销是父
- 遍历 Dictionary,你会几种方式?
- Windows 遍历查找文件夹文件
- 0127循环,替代语法 文本包含
- 原型/类与DOM操作
- 二叉树
- Kotlin-->范围选择进度条, 双向SeekBar
- Android(安卓)Ormlite 学习笔记2 -- 主外键关系