Leetcode-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},

return its zigzag level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Solution:

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
12         List<List<Integer>> res = new ArrayList<List<Integer>>();
13         if (root==null) return res;
14   
15         List<List<TreeNode>> nodeSet = new ArrayList<List<TreeNode>>();
16         List<TreeNode> oneLevel = new ArrayList<TreeNode>();
17         nodeSet.add(oneLevel);
18         oneLevel.add(root);
19         boolean left = false;
20         int index = 0;
21         while (index<nodeSet.size()){
22             List<TreeNode> curLevel = nodeSet.get(index);
23             oneLevel = new ArrayList<TreeNode>();
24             for (int i=curLevel.size()-1;i>=0;i--){
25                 TreeNode curNode = curLevel.get(i);
26                 if (left){
27                     if (curNode.left!=null) oneLevel.add(curNode.left);
28                     if (curNode.right!=null)oneLevel.add(curNode.right);
29                 } else {
30                     if (curNode.right!=null) oneLevel.add(curNode.right);
31                     if (curNode.left!=null) oneLevel.add(curNode.left);
32                 }
33             }
34             if (oneLevel.size()>0) nodeSet.add(oneLevel);
35             left = !left;
36             index++;
37         }
38 
39         for (int i=0;i<nodeSet.size();i++){
40             oneLevel = nodeSet.get(i);
41             List<Integer> oneRes = new ArrayList<Integer>();
42             for (int j=0;j<oneLevel.size();j++)
43                 oneRes.add(oneLevel.get(j).val);
44             res.add(oneRes);
45         }
46 
47         return res;       
48     }
49 }

Solution 2:

We actually only need to store the nodes in the current level.

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
12         List<List<Integer>> resList = new ArrayList<List<Integer>>();
13         if (root==null) return resList;
14         //root level,
15         List<Integer> oneLevel = new ArrayList<Integer>();
16         List<TreeNode> nodeList = new ArrayList<TreeNode>();
17         oneLevel.add(root.val);
18         resList.add(oneLevel);
19         nodeList.add(root);
20         boolean negOrder = true;
21         while (nodeList.size()>0){
22            List<TreeNode> nextNode = new ArrayList<TreeNode>();           
23            //Visit the next level.
24            for (int i=nodeList.size()-1;i>=0;i--){
25                TreeNode cur = nodeList.get(i);
26                if (negOrder){
27                    if (cur.right!=null) nextNode.add(cur.right);
28                    if (cur.left!=null) nextNode.add(cur.left);
29                } else {
30                    if (cur.left!=null) nextNode.add(cur.left);
31                    if (cur.right!=null) nextNode.add(cur.right);
32                }
33            }
34 
35            //If there are nodes in the next level, then put their value into results.
36            if (nextNode.size()>0){
37                oneLevel = new ArrayList<Integer>();
38                for (int i=0;i<nextNode.size();i++) oneLevel.add(nextNode.get(i).val);
39                resList.add(oneLevel);
40            }
41 
42            nodeList = nextNode;
43            negOrder = !negOrder;
44        }
45 
46        return resList;
47         
48     }
49 }