binary tree | 层次遍历相关

102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree `[3,9,20,null,null,15,7]`,

```    3
/ \
9  20
/  \
15   7
```

return its level order traversal as:

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

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root)
return res;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
while(!q.empty())
{
TreeNode* p = q.front();
q.pop();

if(p == nullptr)//每次当p遇到nullptr，就为下一层次的添加一个nullptr
{
res.push_back(cur_vec);
cur_vec.resize(0);
if(q.size() > 0)//最后结束循环的条件是q长度为0
q.push(nullptr);
}
else
{
cur_vec.push_back(p->val);
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
}

}
return res;
}
private:
vector<vector<int>> res;
vector<int> cur_vec;
};``````

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree `[3,9,20,null,null,15,7]`,

```    3
/ \
9  20
/  \
15   7
```

return its bottom-up level order traversal as:

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

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
if(!root)
return res;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
while(!q.empty())
{
TreeNode * p = q.front();
q.pop();
if(p == nullptr)
{
res.insert(res.begin(), cur_vec);//vector 无push_front（）,so use insert()
cur_vec.resize(0);
if(q.size() > 0)
q.push(nullptr);
}
else
{
cur_vec.push_back(p->val);
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
}
}
return res;
}
private:
vector<vector<int>> res;
vector<int> cur_vec;
};``````

103. 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]`,

```    3
/ \
9  20
/  \
15   7
```

return its zigzag level order traversal as:

```[
[3],
[20,9],
[15,7]
]```
``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(!root)
return res;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);

while(!q.empty())
{
TreeNode* p = q.front();
q.pop();

if(p == nullptr)
{
if(Flag == false)//偶数行才处理
{
reverse(cur_vec.begin(), cur_vec.end());
Flag = true;
}
else//奇数行不处理
{

Flag = false;
}
res.push_back(cur_vec);
cur_vec.resize(0);
if(q.size() > 0)
q.push(nullptr);

}
else
{
cur_vec.push_back(p->val);
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
}

}
return res;
}
private:
vector<vector<int>> res;
vector<int> cur_vec;
bool Flag = true;
};``````

;