C++版 - 剑指offer 面试题23：从上往下打印二叉树(二叉树的层次遍历BFS) 题解

剑指offer  面试题23：从上往下打印二叉树

参与人数：4853  时间限制：1秒  空间限制：32768K

提交网址： http://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&tqId=11175

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

分析：

此题即为二叉树的BFS，使用队列可以解决。

AC代码：

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

struct TreeNode

{

	int val;

	TreeNode *left, *right;

	TreeNode(int x): val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

    vector<int> PrintFromTopToBottom(TreeNode *root){

	vector<int> res(0);

    if(root==NULL) return res;

	queue<TreeNode*> q;

	q.push(root);

	while(!q.empty())

	{

		TreeNode *p= q.front();

		res.push_back(p->val);

		q.pop();

		if(p->left != NULL) q.push(p->left);

		if(p->right != NULL) q.push(p->right);

	}

	return res;

    }

};

// 以下为测试

int main()

{

	Solution sol;

	vector<int> res;

	TreeNode *root = new TreeNode(1);

    root->right = new TreeNode(2);

    root->right->left = new TreeNode(3);

	res=sol.PrintFromTopToBottom(root);

	for(int i:res)

		printf("%d ",i);  // 此处为vector遍历的方法，C++11标准支持

	return 0;

}