C++ solution using level traversal(3ms)


  • 0
    M

    It's easy to realize that the solution is the list of last node if each level. So we can use
    "level traversal " to find the last node in each level.

    queue(STL) is generally used in "level traversal" problems. what we need to know is the number of nodes in each level so that the last node can be found easily. Well the number is also easily to be found when we put all the nodes of next level into the queue and there are not nodes in the queue in current level.

    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            queue<TreeNode*> q;
            TreeNode *tmp;
            vector<int> result;
            int level;
        
            if(root != NULL)
                q.push(root);
            while(!q.empty())
            {
                level = q.size(); // the number of nodes in current level
                while(level--)  // find the last node in current level
                {
                    tmp = q.front();
                    q.pop();
                    if(tmp->left != NULL)
                        q.push(tmp->left);
                    if(tmp->right != NULL)
                        q.push(tmp->right);
                }
                result.push_back(tmp->val);
            }
            return result;
        }
    };

Log in to reply
 

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