二叉树的层序遍历，或者说是宽度优先便利，是经常考察的内容。
问题一：层序遍历二叉树并输出，直接输出结果即可，输出格式为一行。
#include <iostream>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <cstdlib> using namespace std; typedef struct BinTree{
int data;
struct BinTree *left;
struct BinTree *right;
}BinTree; /* 按照层序遍历方法遍历二叉树,使用一个队列来辅助 */
void BreadthFirst(BinTree *root){
if(root == NULL)
return;
deque<BinTree *> q;
q.push_back(root); BinTree *p;
while(!q.empty()){
p = q.front();
q.pop_front(); cout<<p->data; if(p->left)
q.push_back(p->left); if(p->right)
q.push_back(p->right);
}
} //测试
int main()
{
/* 创建以下的树
10
/ \
8 2
/ \ /
3 5 2
*/
struct node *root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->left = newNode(2);
iterativePreorder(root);
return 0;
}
问题二： 按层输出二叉树，每一层单独输出为一行。
#include <vector>
#include <deque>
#include <queue> using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; class Solution {
public:
vector<int> rightSideView(TreeNode *root) {
vector<int> ans;
if(root == nullptr) return ans;
queue<TreeNode* > que;
que.push(root); TreeNode* curr;
while(!que.empty()) {
int cnt = que.size();
for(int i = 0; i < cnt; i++) {
curr = que.front();
que.pop();
if(curr->left) {
que.push(curr->left);
}
if(curr->right) {
que.push(curr->right);
}
cout << curr->val << " ";
}
ans.push_back(curr->val);
cout << endl;
}
return ans;
}
}; int main() {
/* 创建以下的树
10
/ \
8 2
/ \ /
3 5 2
*/ Solution sln; TreeNode *root = new TreeNode(10);
root->left = new TreeNode(8);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(2);
sln.rightSideView(root); return 0;
}
LeetCode: Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> result;
if(root == NULL) return result;
deque<TreeNode *> q;
q.push_back(root);
TreeNode *current;
while(!q.empty()) {
int len = q.size();
for(int i = 0; i < len; i++) {
current = q.front();
q.pop_front();
if(current->left) {
q.push_back(current->left);
}
if(current->right) {
q.push_back(current->right);
}
}
result.push_back(current->val);
}
return result;
}
};
同理：可以得到二叉树的左视图求解方式。
vector<int> leftSideView(TreeNode *root)
{
vector<int> ans;
if(root == NULL) return ans;
queue<TreeNode* > que;
que.push(root); TreeNode* curr;
while(!que.empty()) {
int cnt = que.size(); for(int i = 0; i < cnt; i++) {
curr = que.front();
if( i == 0){
ans.push_back(curr->val);
}
que.pop(); if(curr->left) {
que.push(curr->left);
}
if(curr->right) {
que.push(curr->right);
}
}
}
return ans;
}