剑指offer——从上到下打印二叉树

题一：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

class Solution {
public:
	vector levelOrder(TreeNode* root) {
		vector v;  //存放二叉树非空值的数组
		queue q;     //BFS需要用到的队列

		//根节点不为空，入队
		if (root != NULL) {
			q.push(root);
		}
		//层次遍历
		while (!q.empty()) {  
            //每次都遍历完一层
			for (int i = 0; i < q.size(); i++) {
				root = q.front();
				q.pop();
				v.push_back(root->val);
				if (root->left != NULL) {
					q.push(root->left);
				}
				if (root->right != NULL) {
					q.push(root->right);
				}
			}
		}
		return v;
	}
};

题二：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

class Solution {
public:
	vector> levelOrder(TreeNode* root) {
		vector> v;  //存放二叉树非空值的数组
		queue q;     //BFS需要用到的队列

		//根节点不为空，入队
		if (root != NULL) {
			q.push(root);
		}
		//层次遍历
		while (!q.empty()) {
			vector lineV;
            //先记录此时size，即该层的节点数
            int size = q.size();
            //遍历该层
			for (int i = 0; i < size; i++) {

				root = q.front();
				q.pop();

				lineV.push_back(root->val);
				if (root->left != NULL) {
					q.push(root->left);
				}
				if (root->right != NULL) {
					q.push(root->right);
				}
			}
            //将该层的数组存放到二级数组v
			v.push_back(lineV);
		}
		return v;
	}
};

题三：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

class Solution {
public:
	vector> levelOrder(TreeNode* root) {
		vector> v;  //存放二叉树非空值的数组
		deque q;     //BFS需要用到的队列

		//根节点不为空，入队
		if (root != NULL) {
			q.push_back(root);
		}

		int count = 0;

		//层次遍历
		while (!q.empty()) {
			count++;
			vector lineV;
			int size = q.size();

			for (int i = 0; i < size; i++) {

				root = q.front();
				q.pop_front();
				lineV.push_back(root->val);

				if (root->left != NULL) {
					q.push_back(root->left);
				}
				if (root->right != NULL) {
					q.push_back(root->right);
				}
			}
			//偶数层，利用reverse函数该层遍历结果逆置
			if (count % 2 == 0) {
				reverse(lineV.begin(), lineV.end());
			}
			//放入二级数组v中
			v.push_back(lineV);

		}
		return v;
	}
};