[Binary Tree BFS][Medium] 103. Binary Tree Zigzag Level Order Traversal

 

주어진 Binary Tree에 대해 각 level당 value값을 zig zag로 수집하고, 결과를 출력하라. 

 

Solution.

 level의 노드를 문제의 의도대로 교차 접근한다. 

 Easy 난이도에 더 가까운 문제. 

 

 

코드 

vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
{
    vector<vector<int>> vRet;
    if(root == nullptr)    
        return vRet;

    queue<TreeNode*> qBuff;
    qBuff.push(root);
    bool dirLeftToRight = true;
    while(qBuff.size() > 0)
    {
        int cnt = qBuff.size();
        vector<TreeNode*> vLevelNodes;
        for(int q = 0; q < cnt; ++q)
        {
            TreeNode* cur = qBuff.front();
            qBuff.pop();
            vLevelNodes.push_back( cur );
            if(cur->left != nullptr)    qBuff.push(cur->left);
            if(cur->right != nullptr)   qBuff.push(cur->right);
        }

        vector<int> vLevel;
        for(int q = 0; q < vLevelNodes.size(); ++q)
        {
            int idx = dirLeftToRight ? q : vLevelNodes.size()-q-1;
            vLevel.push_back( vLevelNodes[idx]->val );
        }
        vRet.push_back(vLevel);
        dirLeftToRight = !dirLeftToRight;
    }
    return vRet;
}

 

 

결과