Leecode---从上往下打印二叉树

2019-07-23

题目描述

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

思路：

    1
   / \
  2   3
 /   / \
4   5   6
// 打印结果为： [1,2,3,4,null,5,6]
/* 需要用到的队列知识，先进先出
queue<int> q;
q.front(); 返回队列最先进的元素，只返回不删除
q.back(); 返回队末元素
q.pop(); 删除最先进的元素

可以用队列（queue）来做，先把 1 存入队列

从 1 进队列开始：
(1) 出队打印1，再将 1 的左右儿子入队
(2 , 3) 出队打印 2 ，再将 2 的左右儿子入队变成（3 ,4）
(3 , 4) 出队打印3，再将 3 的左右儿子入队变成（4, 5, 6）
以此推出，打印 1 2 3 4 5 6

C++ 代码

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution{
public:
	 vector<int> PrintFromTopToBottom(TreeNode* root){
		vector<int> res;
		if(root == NULL) return res;
		queue<TreeNode*> q; //注意这定义队列时候一定是 TreeNode 结构
		//只有这样才可以用 q.front() 等函数，我们 vector 数组才是要存的 int 类型的 val 
		q.push(root);
		while(q.size()){
			TreeNode* t = q.front();
			res.push_back(t->val);
			q.pop();
			if(t->left) q.push(t->left);
			if(t->right) q.push(t->right);			
		}	
		return res;
	}
};