LeetCode 103. Binary Tree Zigzag Level Order Traversal

原题链接在这里：https://leetcode.com/problems/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,null,null,15,7],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

题解：

这道题是BFS的变形，与Binary Tree Level Order Traversal相似。但是要求偶数行从左到右，奇数行从右到左。

其实还是BFS, 只不过需要添加一个flag来表明是否需要reverse, 这里用boolean reverse 表示.

Time Complexity: O(n).

Space: O(n). que最多有n/2个节点。

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
12         List<List<Integer>> res = new ArrayList<>();
13         if(root == null){
14             return res;
15         }
16         
17         LinkedList<TreeNode> que = new LinkedList<>();
18         que.add(root);
19         boolean reverse = false;
20         
21         while(!que.isEmpty()){
22             int size = que.size();
23             List<Integer> item = new ArrayList<>();
24             while(size-- > 0){
25                 TreeNode cur = que.poll();
26                 item.add(cur.val);
27                 if(cur.left != null){
28                     que.add(cur.left);
29                 }
30                 
31                 if(cur.right != null){
32                     que.add(cur.right);
33                 }
34             }
35             
36             if(reverse){
37                Collections.reverse(item); 
38             }
39             
40             res.add(item);
41             reverse = !reverse;
42         }
43         
44         return res;
45     }
46 }