C++ 7ms BFS O(n) extra space


  • 0
    K
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            vector<int> ans;
            if(!root){
                return ans;
            }
            int lastcount=1;
            queue<TreeNode *> que;
            que.push(root);
            while(!que.empty()){
                while(lastcount >0){
                    TreeNode *tmp = que.front();
                    que.pop();
                    if(tmp->left){
                        que.push(tmp->left);
                    }
                    if(tmp->right){
                        que.push(tmp->right);
                    }
                    lastcount--;
                    if(lastcount==0){
                        ans.push_back(tmp->val);
                    }
                }
                lastcount = que.size();
            }
            return ans;
        }
    };

  • 0
    6

    Why do you think it is O(1) space since you are doing normal bfs with queue?


Log in to reply
 

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