[Binary Tree-BFS][Medium] 199. Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view/description

Binary Tree Right Side View - LeetCode

 

Q. 주어진 tree 에서 가장 우측 노드만 vector에 넣어서 출력하라. 

 

 

Solution

 BFS의 초기 난이도에 해당하는 문제. 

 

BFS를 위해 tree node를 queue에 넣고 빼면서 search한다. (이런 부분은 원리와 함께 암기 해 두는 것이 편하다.)

search과 정중에 해당 depth 당 가장 마지막 노드만, out vector에 push 한다. 

 

vector<int> rightSideView(TreeNode* root)
{
    vector<int> vRet;
    if (root == NULL)    return vRet;

    queue<TreeNode*> qBuff;
    qBuff.push(root);

    while (!qBuff.empty())
    {
        int size = qBuff.size();
        for (int q = 0; q < size; ++q)
        {
            TreeNode* cur = qBuff.front();
            qBuff.pop();

            if (q == size - 1)
                vRet.push_back(cur->val);

            if (cur->left != NULL)	qBuff.push(cur->left);
            if (cur->right != NULL)	qBuff.push(cur->right);
        }
    }
    return vRet;
}

 

 

결과.