Leetcode 103. Binary Tree Zigzag Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal

Total Accepted: 64518 Total Submissions: 219636 Difficulty: Medium

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

1  3
2    / 
3   9  20
4     /  
5    15   7

return its zigzag level order traversal as:

1 [
2   [3],
3   [20,9],
4   [15,7]
5 ]

思路：

代码：

先层序遍历，然后将编号为奇数（从0开始）的vector中元素反转。

方法一：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
13         queue<TreeNode*> q;
14         vector<vector<int>> res;
15         if(root==NULL){
16             return res;
17         }
18         q.push(root);
19         q.push(NULL);
20         vector<int> temp;
21         bool even=true;
22         while(!q.empty()){
23             TreeNode* cur=q.front();
24             q.pop();
25             if(cur){
26                 temp.push_back(cur->val);
27                 if(cur->left) q.push(cur->left);
28                 if(cur->right) q.push(cur->right);
29             }
30             else{
31                 even=!even;
32                 res.push_back(temp);
33                 if(q.size()>0){
34                     temp.resize(0);
35                     q.push(NULL);
36                 }
37             }
38         }
39         for(int i=0;i<res.size();i++){
40             if(i%2){
41                 reverse(res[i].begin(),res[i].end());
42             }
43         }
44         return res;
45     }
46 };

方法二：

 1 class Solution {
 2 public:
 3     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
 4         queue<TreeNode*> q;
 5         vector<vector<int>> res;
 6         if(root==NULL){
 7             return res;
 8         }
 9         q.push(root);
10         q.push(NULL);
11         vector<int> temp;
12         bool even=true;
13         while(!q.empty()){
14             TreeNode* cur=q.front();
15             q.pop();
16             if(cur){
17                 if(even){
18                     temp.push_back(cur->val);
19                 }
20                 else{
21                     temp.insert(temp.begin(),cur->val);
22                 }
23                 if(cur->left) q.push(cur->left);
24                 if(cur->right) q.push(cur->right);
25             }
26             else{
27                 even=!even;
28                 res.push_back(temp);
29                 if(q.size()>0){
30                     temp.resize(0);
31                     q.push(NULL);
32                 }
33             }
34         }
35         return res;
36     }
37 };