[数据结构与算法]4. 二叉树的层序遍历 (levelOrder)

头文件：　用到的是前序遍历中的头文件，具体可参见 "二叉树的前序遍历"

一，层序遍历的概念

????????层序遍历
????????????????实质是 广度优先搜索，按照层的顺序访问每个节点
????????????????可以利用队列的性质，逐层访问

二，层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> ret;
	if (root) {
		queue<TreeNode*> queue;
		queue.emplace(root);

		while (!queue.empty()) {		// 队列不空
			int size = queue.size();	// 获取队列中的元素个数，表示当前这层的元素个数
			vector<int> vec;

			for (int i = 0; i < size; i++) {// 将当前这层所有的元素都弹出来，将弹出元素的子节点加入到队列中
				TreeNode* top = (TreeNode*)queue.front();	// 获取当前的元素
				queue.pop();
				vec.emplace_back(top->val);			// 弹出过程中，记录这层所包含的元素

				if (top->left) {		// 若该元素有左儿子，则将其加入队列
					queue.emplace(top->left);
				}
				if (top->right) {		// 若该元素有右儿子，则将其加入队列
					queue.emplace(top->right);
				}
			}
			if (!vec.empty()) {			// 记录这层元素的 vector 不为空，则将其加入结果
				ret.emplace_back(vec);
			}
		}
	}
	return ret;
}

三，主函数

#if LEVEL_ORDER_TRAVERSAL

int main() {

	//TreeNode* root = getRandomTree();

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

	root->left->left = new TreeNode(4);
	root->left->right = new TreeNode(5);

	root->right->left = new TreeNode(6);
	root->right->right = new TreeNode(7);

	vector<vector<int>> ret = levelOrder(root);

	cout << "层序遍历 : " << endl;
	for (int i = 0; i < ret.size(); i++) {
		PRINT(ret[i]);
	}

	return 0;
}

#endif