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,#,#,15,7}
,
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
很常规的题目,要求按层输出结点。如果只用一个队列的话,需要给每个结点额外定义一个bool变量用来区分不同层。如果不想另外定义变量的话,可以使用两个队列,对于不同层交替使用。swap方法可以完成两个队列的交替。
/**
* Definition for binary tree
* 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) {
vector<vector<int>> levels;
if(!root) return levels;
queue<TreeNode*> curque, nextque;
vector<int>* lev = new vector<int>();
curque.push(root);
while(!curque.empty()){
TreeNode* curNode = curque.front();
curque.pop();
lev -> push_back(curNode -> val);
if(curNode -> left) nextque.push(curNode -> left);
if(curNode -> right) nextque.push(curNode -> right);
if(curque.empty()){
levels.push_back(*lev);
lev = new vector<int>();
swap(curque, nextque);
}
}
return levels;
}
};
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]
]
因为需要一层层地遍历,所以依然使用广度搜索,但是因为输出顺序的特殊性,我们需要对每层建一个缓存。
第一反应是使用queue的同时,再用一个stack 存储每一层的节点,用以逆序。
这种思路稍稍简化一下,可以改为使用两个stack,交替使用。
两个stack可以放到数组中,创建方法见代码。
这一次我不再使用swap,而是使用一个数组,然后通过判断奇偶来切换。
/**
* Definition for binary tree
* 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) {
vector<vector<int>> levels;
if(!root) return levels;
stack<TreeNode*>* stacks = new stack<TreeNode*>[]; //stack 数组
int i = ;
vector<int>* lev = new vector<int>(); //用来存储每一层的值
stacks[].push(root);
while(!stacks[i&].empty()){
TreeNode* node = stacks[i&].top();
stacks[i&].pop();
lev -> push_back(node -> val);
if(i&){
if(node -> right) stacks[-i&].push(node -> right);
if(node -> left) stacks[-i&].push(node -> left);
}else{
if(node -> left) stacks[-i&].push(node -> left);
if(node -> right) stacks[-i&].push(node -> right);
}
if(stacks[i&].empty()){
++i;
levels.push_back(*lev);
lev = new vector<int>(); //给指针赋新的对象,存放下一层的值
}
}
return levels;
}
};