4ms AC (in C++) level-order based solution. w/ explanation


  • 0
    A

    Basically we're required to print the rightmost node in each level.
    I did a level-order traversal of the tree starting from the root maintaining a deque of TreeNode pointers corresponding to each node. We maintain a pushcount and popcount (counters for the pushes performed for each node in the deque) and intuitively for a level order the number of pushes into the deque due to the previous level's nodes is the number of nodes in the next level.
    If root == NULL there's obviously no solution. Otherwise start by pushing *root (popcount = 1 for the pushed root)

    Now we iteratively do the following until the deque becomes empty.

    popcount indicates the number pop_front() required to complete the current level.

    While popping a TreeNode from the deque we check the left and right pointers. If they are NOT NULL we push them to the deque. (increment pushcount )

    The last pop ie popcount == 1 would be the rightmost Node in that level. So do a push_back() to the returning vector. ( we can also do Binary Tree left side view by printing for the first pop instead of the last pop )

    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            if(!root) {return{};}
            deque<TreeNode*> level;
            TreeNode* curr = root;
            level.push_back(curr);
            int pushcount=0,popcount=1;
            vector<int> ret;
            while(!level.empty()){ // repeating till you've exhausted all the TreeNodes
                while(popcount !=0){ //repeating till you've exhausted the TreeNodes for the current level.
                    TreeNode* temp = level.front();
                    //if children != NULL push to deque
                    if(temp->left!=NULL){ 
                        level.push_back(temp->left);
                        pushcount++;
                    }
                    if(temp->right!=NULL){
                        level.push_back(temp->right);
                        pushcount++;
                    }
                    if(popcount == 1) ret.push_back(temp->val); // last pop has the rightmost node
                    level.pop_front();
                    popcount--;
                }
                popcount = pushcount;
                pushcount = 0;
            }
            return ret;
        }
    };
    

    popcount = pushcount and pushcount = 0 are done to repeat for the next level of TreeNodes.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.