My simple C++ tree method solution, easy to understand


  • 0
    J
    vector<string> generateParenthesis(int n)
    {
    	vector<string> result;
    	if (n >= 1)
    	{
    		vector<string> x;
    		vector<int> leftCts;
    		vector<int> rightCts;
    
    		x.push_back("(");
    		leftCts.push_back(1);
    		rightCts.push_back(0);
    
    		int k = 1; // k stores number of nodes generated so far
    		int i = 0; // i points to the node to be checked
    
    		while (i < k) // While there is still node to be checked
    		{
    			// Check whether i points to a leaf node
    			if ((leftCts[i] == n) & (rightCts[i] == n))
    				result.push_back(x[i]);
    			// If not leaf node, add left child or right child
    			if (leftCts[i] < n) // The condition for adding left child
    			{
    				// Generate left child
    				x.push_back(x[i]+"(");
    				leftCts.push_back(leftCts[i]+1); // Left count = parent's left count + 1
    				rightCts.push_back(rightCts[i]); // Right count remains the same as the parent
    				k++;
    			}
    			if (rightCts[i] < leftCts[i]) // The condition for adding right child
    			{
    				// Generate right child
    				x.push_back(x[i]+")");
    				leftCts.push_back(leftCts[i]); // Left count remains the same as the parent
    				rightCts.push_back(rightCts[i]+1); // Right count = parent's right count + 1
    				k++;
    			}
    			i++; // To check the next tree node in x[]
    		}
    
    	}
    
    	return (result);
    }

Log in to reply
 

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