[LeetCode][Java] Binary Tree Zigzag Level Order Traversal

题目：

Given a binary tree, return thezigzag level ordertraversal 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]]题意：

给定一棵二叉树，返回这棵树的节点的’Z’字形遍历（即 起始顺序为先左后右，下一层的顺序为先右后左，这样交替进行）

比如

给定二叉树{3,9,20,#,#,15,7},

3 / \ 9 20/ \ 15 7返回这棵树的’z’字形遍历：[ [3], [20,9], [15,7]]算法分析：

利用题目《Binary Tree Level Order Traversal》的结果，对ArrayList中的奇数元素进行倒序 。难度不大，直接上代码

AC代码：

<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution {public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root){ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();if (root == null)return list;list = levelOrder(root);for(int i=1;i<list.size();i+=2){reverse(list.get(i));}return list;}private static void reverse(ArrayList<Integer> temlist){int tem=0;int temsize=0;if(temlist.size()%2==0)temsize=temlist.size()/2-1;elsetemsize=temlist.size()/2;for(int i=0;i<=temsize;i++){tem=temlist.get(i);temlist.set(i, temlist.get(temlist.size()-1-i));temlist.set(temlist.size()-1-i, tem);}} public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();if (root == null){return res;}ArrayList<Integer> tmp = new ArrayList<Integer>();Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int num;boolean reverse = false;while (!queue.isEmpty()){num = queue.size(); //每次通过这个确定最终的出队数目tmp.clear();for (int i = 0; i < num; i++) //队列中出1个父，进两个子；出2个父，进4个子；出4个父，进8个子{TreeNode node = queue.poll();tmp.add(node.val);if (node.left != null)queue.offer(node.left);if (node.right != null)queue.offer(node.right);}res.add(new ArrayList<Integer>(tmp));}return res;} }</span>

版权声明：本文为博主原创文章，，转载注明出处

躲在某一地点，想念一个站在来路，