[Leetcode] Binary Tree Right Side View

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Given the following binary tree,

 1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Analysis:
BFS level traversal and print last node on each level. A tricky part is how to find out last node on that part easily.  We can insert 'dummy' nodes between levels, or, Introducing two variables 'count' and 'nextcount' makes it easier. 

Solution:
    void bfs(TreeNode *root, vector<int> &result)
    {
        if(root == NULL)
           return;           
        queue<TreeNode *> nodes;

        nodes.push(root);
        int count = 1, nextcount = 0;  ->  Init count to 1 for root, nextcount to zero

        while(!nodes.empty())
        {
            TreeNode *current = nodes.front();
            nodes.pop();
            if(current != NULL)
            {
                count--;                         - > Reduce count for node(s) on current level
                if(current->left)
                {
                    nodes.push(current->left);
                    nextcount++;             - > Increase count for node(s) on next level
                }
                if(current->right)
                {
                    nodes.push(current->right);
                    nextcount++;            - > Increase count for node(s) on next level
                }
                
                // reaching last node at the level, add it to the output
                if(count == 0)               - > When count is 0, meaning we reach last node on that level 
                {
                    result.push_back(current->val);
                    count = nextcount;    - > Now assign node(s) count from next level to next 'current' level
                    nextcount = 0;
                }           
            }
        }
    }

Final thoughts:
  How about left view of the tree ? We can print first node on each level instead of the last.
  Introducing a new variable 'flag' to do the trick.

void bfs(TreeNode *root, vector<int> &result)
    {
        if(root == NULL)
           return;           
        queue<TreeNode *> nodes;

        nodes.push(root);
        int count = 1, nextcount = 0;  ->  Init count to 1 for root, nextcount to zero
        int flag = 1;                            ->  Init flag to 1
        while(!nodes.empty())
        {
            TreeNode *current = nodes.front();
            nodes.pop();
            if(current != NULL)
            {
               if(flag)
               {
                    result.push_back(current_val);    ->  First node on that level, print and reset flag
                    flag = 0;
               } 
               count--;                         
                if(current->left)
                {
                    nodes.push(current->left);
                    nextcount++;             
                }
                if(current->right)
                {
                    nodes.push(current->right);
                    nextcount++;           
                }

                if(count == 0)              
                {
                   flag = 1;               ->  Last node at current level, next node starts from first node of next level, hence set flag back to 1
                    count = nextcount;    
                    nextcount = 0;
                }           
            }
        }
    }