My O(n) solution, 9ms


  • 1
    vector<vector<int> > BiTreeLevelOrderTraversal::levelOrder(TreeNode *root)
    {
    	vector<vector<int> > result;
    	vector<int> temp;
    	vector<TreeNode*> current;
    	vector<TreeNode*>::iterator it;
    
    	if( root == NULL )
    		return result;
    	
    	temp.push_back(root->val);
    	result.push_back(temp);
    	temp.clear();
    	current.push_back( root );
    
    	while ( current.size() != 0 )
    	{
    		vector<TreeNode*> parent(current); //get a copy of current
    		current.clear(); //a new current
    		for( it = parent.begin(); it != parent.end(); it++ )
    		{
    			//get all the previous level node
    			if( (*it)->left != NULL)
    			{
    				temp.push_back(((*it)->left)->val);
    				current.push_back((*it)->left);
    			}
    			if ( (*it)->right != NULL )
    			{
    				temp.push_back(((*it)->right)->val);
    				current.push_back((*it)->right);
    			}
    		}
    		//if we get nothing, we should not add an empty
    		if( temp.size() != 0 )
    		{
    			result.push_back( temp );
    			temp.clear();
    		}
    		parent.clear();
    
    	}
    
    }

Log in to reply
 

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