二叉树结构：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
二叉树宽度优先搜索：
按照二叉树的层数依次从左到右访问二叉树的节点；
例如：给定一个二叉树：
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
按照宽度优先搜索得到：
第一层根节点：5
第二层从左到右：4->8
第三层从左到右：11->13->4
第四层从左到右：7->2->5->1
最后输出：5->4->8->11->13->4->7->2->5->1；
ok，接下来考虑要如何编程实现这一问题：
分析：
遍历过程：
- 输入根节点5；
- 依次判断根节点5的左节点和右节点是否存在：
左节点存在，输入左节点4；右节点存在，输入右节点8；
第二层遍历结束； - 从左到右遍历第三层，所以应该先判断节点4；
左节点存在，输入左节点11；右节点不存在； - 继续向右遍历第三层，判断节点8；
左节点存在，输入左节点13；右节点存在，输入右节点4；
第三层遍历结束； - 同上，直到遍历结束；
综上，我们发现，我们是按照节点存入的顺序来判断当前节点的左右节点是否存在的，先存入的节点先判断（先进先出），所以我们用队列（queue）来实现二叉树的宽度优先搜索；
程序设计：
- 队列存储根节点；
- 判断队列的头节点是否存在左右节点：存在，将节点加入队列中；此时，头结点的左右节点判断存储完成，删除队列头结点；
- 同上，当队列中的所有节点全部判断完成时，队列为空，遍历结束；
程序实现(C/C++)：
#include <cstdio>
#include <iostream>
#include <vector>
#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) {
queue<TreeNode *> q;
vector<int> result;
q.push(root);
while (!q.empty()) {
if (q.front()->left) {
q.push(q.front()->left);
}
if (q.front()->right) {
q.push(q.front()->right);
}
result.push_back(q.front()->val);
q.pop();
}
return result;
}
};
int main() {
TreeNode a(5);
TreeNode b(4);
TreeNode c(8);
TreeNode d(11);
TreeNode e(13);
TreeNode f(4);
TreeNode g(7);
TreeNode h(2);
TreeNode i(5);
TreeNode j(1);
a.left = &b;
b.left = &d;
d.left = &g;
d.right = &h;
a.right = &c;
c.left = &e;
c.right = &f;
f.left = &i;
f.right = &j;
Solution s;
vector<int> result;
result = s.rightSideView(&a);
for (int i = 0; i < result.size(); i++) {
printf("%d->", result[i]);
}
return 0;
}
结果：
5->4->8->11->13->4->7->2->5->1->
