#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) return {};
        vector<vector<int>> ans;
        typedef pair<TreeNode*, int> PAIR;
        queue<PAIR>que;
        //pair 的第二个元素表示结点位于第几层
        que.push(PAIR(root, 0));
        while(!que.empty()) {
            PAIR curt = que.front();
            que.pop();
            if(ans.size() <= curt.second) {
                ans.push_back(vector<int>());
            }
            ans[curt.second].push_back(curt.first->val);
            if(curt.first->left) {
                que.push(PAIR(curt.first->left, curt.second + 1));
            }

            if(curt.first->right) {
                que.push(PAIR(curt.first->right, curt.second + 1));
            }
        }
        return ans;
    }
};

/**
 * 创建二叉树，用于测试
 */
TreeNode* createBinary() {
    TreeNode* root = new(TreeNode);
    TreeNode* p1 = new(TreeNode);
    TreeNode* p2 = new(TreeNode);
    TreeNode* p3 = new(TreeNode);
    TreeNode* p4 = new(TreeNode);

    root->left = p1;
    root->right = p2;
    root->val = 3;

    p1->left = nullptr;
    p1->right = nullptr;
    p1->val = 9;

    p2->left = p3;
    p2->right = p4;
    p2->val = 20;

    p3->left = nullptr;
    p3->right = nullptr;
    p3->val = 15;

    p4->left = nullptr;
    p4->right = nullptr;
    p4->val = 7;
    return root;
}

int main()
{
    TreeNode* root = createBinary();

    Solution obj;
    vector<vector<int>> ans = obj.levelOrder(root);

    //输出结果
    for(int i = 0; i < (int)ans.size(); ++i) {
        for(int j = 0; j < (int)ans[i].size(); ++j) {
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

3
9 20
15 7