Binary Tree ZigZag Level Order Traversal leetcode java

浏览数：29 / 时间：2015年06月08日

题目：

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，用一个flag记录是否需要reverse，如果需要的话就把reverse的结果存储即可。
代码如下：

1     public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
2         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
3
4         if(root==null)
5             return res;
6
7         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
8         queue.add(root);
9
10         int num = 0;
11         boolean reverse = false;//a flag
12
13         while(!queue.isEmpty()){
14             num = queue.size();
15             ArrayList<Integer> levelres = new ArrayList<Integer>();
16
17             for(int i = 0; i<num; i++){
18                 TreeNode node = queue.poll();
19                 levelres.add(node.val);
20
21                 if(node.left!=null)
22                     queue.add(node.left);
23                 if(node.right!=null)
24                     queue.add(node.right);
25             }
26
27             if(reverse){
28                 Collections.reverse(levelres);
29                 reverse = false;
30             }else{
31                 reverse = true;
32             }
33             res.add(levelres);
34         }
35
36         return res;
37     }

Binary Tree ZigZag Level Order Traversal leetcode java,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Binary Tree ZigZag Level Order Traversal leetcode java