这里是LeetCode BFS类型前半部分题目:
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]
]
struct ZigZag{
TreeNode *node;
int level;
ZigZag(TreeNode *p, int n) : node(p), level(n){}
};
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector <vector<int> > v;
ZigZag pz(NULL,0);
stack<ZigZag> sz;
int child_level = 0;
if (root)
{
sz.push(ZigZag(root,0));
}
while (!sz.empty())
{
pz = sz.top();
sz.pop();
if (v.size() < pz.level + 1)
{
vector<int> tmp_v;
v.push_back(tmp_v);
}
if (pz.level % 2 == 1)
{//from right to left
v[pz.level].push_back(pz.node->val);
}
else
{//from left to right
v[pz.level].insert(v[pz.level].begin(), pz.node->val);
}
if (pz.node->left)
{
sz.push(ZigZag(pz.node->left, pz.level + 1));
}
if (pz.node->right)
{
sz.push(ZigZag(pz.node->right, pz.level + 1));
}
}
return v;
}
};
zigzag遍历很简单,但是我封装了TreeNode,新造了一个数据结构ZigZag来保存每一个节点的层次,不够优雅,有没有什么方法不用封装呢,看下面。
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,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
vector<vector<int> > levelOrder(TreeNode *root)
{
vector<vector<int> > v;
typedef pair<TreeNode*, int> PAIR;
queue<PAIR> q;
if (root)
{
q.push(PAIR(root, 0));
}
while (!q.empty())
{
TreeNode *node = q.front().first;
int level = q.front().second;
q.pop();
if (v.size() < level + 1)
{
vector<int> item;
v.push_back(item);
}
v[level].push_back(node->val);
if (node->left)
{
q.push(PAIR(node->left, level + 1));
}
if (node->right)
{
q.push(PAIR(node->right, level + 1));
}
}
return v;
}
这里用pair
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,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
将Binary Tree Level Order Traversal 返回的数组reverse一下就可以了。
vector<vector<int> > levelOrderBottom(TreeNode *root)
{
vector<vector<int> > v;
typedef pair<TreeNode*, int> PAIR;
queue<PAIR> q;
if (root)
{
q.push(PAIR(root, 0));
}
while (!q.empty())
{
TreeNode *node = q.front().first;
int level = q.front().second;
q.pop();
if (v.size() < level + 1)
{
vector<int> item;
v.push_back(item);
}
v[level].push_back(node->val);
if (node->left)
{
q.push(PAIR(node->left, level + 1));
}
if (node->right)
{
q.push(PAIR(node->right, level + 1));
}
}
//reverse v
int n = v.size();
for (int i = 0; i < n / 2; i++)
{
v[i].swap(v[n - 1 - i]);
}
return v;
}
在DFS系列里已经解决了这个问题==Clone Graph