【BFS】N 叉树的层序遍历 / 二叉树的锯齿形层序遍历 / 二叉树最大宽度 / 在每个树行中找最大值

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        queue<Node*> q;
        q.push(root);
        while (!q.empty())
        {
            vector<int> tmp;
            int size = q.size();
            while (size--)
            {
                tmp.push_back(q.front()->val);
                for (auto e : q.front()->children)
                {
                    q.push(e);
                }
                q.pop(); // 利用父节点把子节点全部插入队列后再删除父节点
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);
        int flag = 1;
        while (!q.empty())
        {
            int size = q.size();
            vector<int> tmp;
            while (size--)
            {
                auto t = q.front();
                tmp.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
                q.pop();
            }
            flag *= -1;
            if (flag > 0) reverse(tmp.begin(), tmp.end());
            ret.push_back(tmp);
        }
        return ret;
    }
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        vector<pair<TreeNode*, unsigned int>> q; 
        q.push_back({root, 1});
        unsigned int ret = 0;
        while (!q.empty())
        {
            auto &[x1, y1] = q.front();
            auto &[x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);
            vector<pair<TreeNode*, unsigned int>> tmp;
            for (auto &[a, b] : q)
            {
                if (a->left) tmp.push_back({a->left, 2 * b});
                if (a->right) tmp.push_back({a->right, 2 * b + 1});
            }
            q = tmp;
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int sz = q.size(), m = INT_MIN;
            while (sz--)
            {
                auto t = q.front();
                q.pop();
                m = max(m, t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            ret.push_back(m);
        } 
        return ret;
    }
};