题解 | #牛群分层排列# 层序遍历

知识点

层序遍历 二叉树

思路分析

把二叉树同一层的值拼接成一个字符串，然后把这些字符串返回。

很经典的层序遍历题，我们只需要对二叉树跑层序遍历，把每次遍历到的val加入到对应的字符串中即可。在遍历的过程中遇到第一次出现的层的值，需要建立一个新的位置的空串来拼接，这里我是写的while循环（实际上最多只会执行一次，写if也可以），这个的原因是因为层序遍历实际上也是一种BFS，在同一时间之内，queue中的idx最多只会差1。

时间复杂度

层序遍历，访问每个结点各一次，时间复杂度

vector每次插入的时间复杂度可以均摊为常数的。

整体时间复杂度

AC code （C++）

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
#include <queue>
#include <utility>

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return string字符串vector
     */
    using pti = pair<TreeNode*, int>;
    vector<string> levelOrder(TreeNode* root) {
        // 层序遍历
        vector<string> res;
        queue<pti> q;
        if (root) q.emplace(root, 0);
        while (q.size()) {
            auto [p, idx] = q.front();
            q.pop();
            while (res.size() <= idx) res.push_back(""); // 每次最多执行一次
            res[idx] += to_string(p->val);
            if (p->left) q.emplace(p->left, idx + 1);
            if (p->right) q.emplace(p->right, idx + 1);
        }
        return res;
    }
};