二叉树的层序遍历

二叉树的层序遍历

一、题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）

但是有一个条件，每一层输出一行。

Leetcode：https://leetcode.cn/problems/binary-tree-level-order-traversal/

二、思路

一般的层序遍历比较简单，只需要使用一个队列，但是现在加上一个条件，即每一层按行打印。因此我们就需要知道每一行的最右边的节点，然后做换行操作。那么如何得知每一行最右边的节点呢？首先我们知道 root 节点，即根节点为第一层的最右节点。使用两个变量，一个记录当前层的最右节点，记为 last；另一个记录下一层的最右节点，记为 nlast。而我们在遍历每个节点时，都去判断当前节点是否为当前层的最右节点即可。如果已经遍历到当前层的最右节点了，那么下一层的最右节点其实也已经被赋值了。此时将下一层的最右节点 nlast 赋给 last 即可。

三、code

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

void level_recur(TreeNode* root) {
	if (root == nullptr) {
		return;
	}
	TreeNode* last = root;
	TreeNode* nlast = nullptr;
	std::queue<TreeNode*> qu;
	qu.push(root);
	int count = 1;
	std::cout << "level " << count << ": ";
	while (!qu.empty()) {
		TreeNode* node = qu.front();
		qu.pop();
		std::cout << node->val << " ";
		if (node->left) {
			qu.push(node->left);
			nlast = node->left;
		}
		if (node->right) {
			qu.push(node->right);
			nlast = node->right;
		}
		if (node == last && !qu.empty()) {
			std::cout << std::endl << "level " << count++ << ": ";
			last = nlast;
		}
	}
	std::cout << std::endl;
}