首页 > 代码库 > [leetcode]Binary Tree Zigzag Level Order Traversal
[leetcode]Binary Tree Zigzag Level Order Traversal
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree{3,9,20,#,#,15,7},3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]
算法思路：
BFS，没什么好讲的，用一个boolean变量标记是正序还是逆序，逆序就用头插法，正序用尾插法。
代码如下：
1 public class Solution { 2 List<List<Integer>> res = new ArrayList<List<Integer>>(); 3 public List<List<Integer>> zigzagLevelOrder(TreeNode root) { 4 if(root == null) return res; 5 Queue<TreeNode> q = new LinkedList<TreeNode>(); 6 Queue<TreeNode> copy = new LinkedList<TreeNode>(); 7 q.offer(root); 8 res.add(new ArrayList<Integer>(Arrays.asList(root.val))); 9 boolean tag = false;10 while(!q.isEmpty()){11 TreeNode tem = q.poll();12 if(tem.left != null) copy.offer(tem.left);13 if(tem.right != null) copy.offer(tem.right);14 if(q.isEmpty() && !copy.isEmpty()){15 List<Integer> list = new LinkedList<Integer>();16 if(tag){17 while(!copy.isEmpty()){18 q.add(copy.peek());19 list.add(copy.poll().val);20 }21 }else{22 while(!copy.isEmpty()){23 q.add(copy.peek());24 list.add(0, copy.poll().val);25 }26 }27 res.add(list);28 tag = !tag;29 }30 }31 return res;32 }33 }
我用了两个queue来进行层次的区分，网上很多人很巧妙的用了一个null来表示一层的结束。请参考这里。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。