2014
11-18

# 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]
]


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

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1
/ \
2   3
/
4
\
5


The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

// LeetCode, Binary Tree Zigzag Level Order Traversal
// 递归版，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> result;
traverse(root, 1, result, true);
return result;
}

void traverse(TreeNode *root, size_t level, vector<vector<int>> &result,
bool left_to_right) {
if (!root) return;

if (level > result.size())
result.push_back(vector<int>());

if (left_to_right)
result[level-1].push_back(root->val);
else
result[level-1].insert(result[level-1].begin(), root->val);

traverse(root->left, level+1, result, !left_to_right);
traverse(root->right, level+1, result, !left_to_right);
}
};


//LeetCode, Binary Tree Zigzag Level Order Traversal
//广度优先遍历，用一个bool记录是从左到右还是从右到左，每一层结束就翻转一下。
// 迭代版，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int> > result;
if (nullptr == root) return result;

queue<TreeNode*> q;
bool left_to_right = true;  //left to right
vector<int> level;  // one level's elements

q.push(root);
q.push(nullptr);  // level separator
while (!q.empty()) {
TreeNode *cur = q.front();
q.pop();
if (cur) {
level.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
} else {
if (left_to_right) {
result.push_back(level);
} else {
reverse(level.begin(), level.end());
result.push_back(level);
}
level.clear();
left_to_right = !left_to_right;

if (q.size() > 0) q.push(nullptr);
}
}

return result;
}
};


Java代码:

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if(root == null) return ans;
boolean isOdd = false;
TreeNode flag = new TreeNode(0);
Queue<TreeNode> q = new ArrayDeque<TreeNode>();
List<Integer> tmp = new ArrayList<Integer>();
while(q.size() > 1){
TreeNode top = q.poll();
//System.out.println(top.val);
if(top == flag){
if(isOdd){
Collections.reverse(tmp);
}
tmp = new ArrayList<Integer>();
isOdd = !isOdd;
}else{
if(top.left != null) q.add(top.left);
if(top.right != null) q.add(top.right);
}
}
return ans;
}
}

1. 我遇到过类似的情况。一把双头的刻刀，从桌上掉下来，我下意识双腿一夹。夹是夹住了，但是横着被双腿夹住的，你们感受下。

2. 我遇到过类似的情况。一把双头的刻刀，从桌上掉下来，我下意识双腿一夹。夹是夹住了，但是横着被双腿夹住的，你们感受下。

3. 我遇到过类似的情况。一把双头的刻刀，从桌上掉下来，我下意识双腿一夹。夹是夹住了，但是横着被双腿夹住的，你们感受下。

4. 我遇到过类似的情况。一把双头的刻刀，从桌上掉下来，我下意识双腿一夹。夹是夹住了，但是横着被双腿夹住的，你们感受下。

5. 我遇到过类似的情况。一把双头的刻刀，从桌上掉下来，我下意识双腿一夹。夹是夹住了，但是横着被双腿夹住的，你们感受下。

6. 我遇到过类似的情况。一把双头的刻刀，从桌上掉下来，我下意识双腿一夹。夹是夹住了，但是横着被双腿夹住的，你们感受下。

7. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}

8. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

9. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

10. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。