9ms C++ BFS, O(n) time, concise with explanation


  • 12

    9ms C++ iterative, concise code with explanation

    Using a queue mQ to perform level order traversal. In the beginning of a level traversal, the last element is pushed into result array ret. The core idea is similar with Binary Tree Level Order Traversal

    O(n) time, O(logn) space

    class Solution {
    public:
        vector<int> rightSideView(TreeNode *root) {
            queue<TreeNode*>mQ;
            vector<int> ret;
            if(!root)return ret;
            mQ.push(root);
            while(!mQ.empty()){
                ret.push_back(mQ.back()->val);
                for(int i=mQ.size();i>0;i--){
                    TreeNode *tn=mQ.front();
                    mQ.pop();
                    if(tn->left)mQ.push(tn->left);
                    if(tn->right)mQ.push(tn->right);
                }
            }
            return ret;
        }
    };
    

  • -1

    space is O(logn), because it stores around one-level nodes.


  • 0

    You are right, the space is O(logn) rather than O(n). I will change it. Thanks for pointing that out.


  • 4
    M

    Nope, the space is O(n) for the worst case of balanced tree. In that case, the last level would store half the number of total nodes.


  • 0
    S
    vector<int> rightSideView(TreeNode* root) {
    	vector<int> out;
    	if (root == nullptr)
    		return out;
    	queue<TreeNode*> que;
    	que.push(root);
    	queue<TreeNode*>::size_type end = que.size();
    	while (!que.empty())
    	{
    		out.push_back(que.back()->val);
    		while (end--)
    		{
    			TreeNode *pop = que.front();
    			que.pop();
    			if (pop->left != nullptr)
    				que.push(pop->left);
    			if (pop->right != nullptr)
    				que.push(pop->right);
    		}
    		end = que.size();
    	}
    	return out;
    }

  • 0
    S
    This post is deleted!

  • 0
    S

    @bo28 Not exactly.the worst space complex is O(n),since the number of leaf nodes of a perfect binary tree is n/2+1.


Log in to reply
 

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