[c++] leetcode, 102. Binary Tree Level Order Traversal

Tree의 같은 level의 노드들의 value를 묶어서 출력하는 문제이다.

같은 level은 search하는 방법인 BFS이므로, queue를 이용하여 문제를 풀어준다.

class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> answer;
        queue<pair<TreeNode *, int>> q;
        if (root != nullptr)
        {
            q.push({root, 0});
        }

        int curIdx = -1;
        while (!q.empty())
        {
            pair<TreeNode *, int> top = q.front();
            q.pop();
            if (curIdx < top.second)
            {
                curIdx++;
                vector<int> a;
                answer.push_back(a);
            }
            answer[top.second].push_back(top.first->val);
            if (top.first->left != nullptr)
            {
                q.push({top.first->left, top.second + 1});
            }
            if (top.first->right != nullptr)
            {
                q.push({top.first->right, top.second + 1});
            }
        }
        return answer;
    }
};