LeetCode之Generate Parentheses（C++）

forrestlin

发布于 2018-05-24 03:25:40

43100

代码可运行

文章被收录于专栏：蜉蝣禅修之道蜉蝣禅修之道

运行总次数：0

代码可运行

题目：Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

目标：生成正确的括号对

数据结构：采用二叉树结构，每个节点的value是“（”或“）”，节点结构包括左右孩子节点，父节点，val，栈顶节点，剩下可使用的“（”的数量count，代码表示如下：

        struct TreeNode{
		TreeNode* left,*right,*parent,*top;
		char val;
		int count;
		TreeNode(char v):val(v),top(NULL),left(NULL),right(NULL),parent(NULL),count(0){};
		TreeNode(char v,TreeNode* p):val(v),top(NULL),left(NULL),right(NULL),parent(p),count(0){};
	};

算法思路：当当前节点的栈顶节点为“（”时，可以插入右子节点“）”，此时若count大于0，还可以插入左子节点“（”，当栈顶节点为空时，且count大于0，那么可以插入左子节点“（”，否则只能返回。以上插入完子节点后均可以继续递归。完整代码如下：

class Solution {
public:
	struct TreeNode{
		TreeNode* left,*right,*parent,*top;
		char val;
		int count;
		TreeNode(char v):val(v),top(NULL),left(NULL),right(NULL),parent(NULL),count(0){};
		TreeNode(char v,TreeNode* p):val(v),top(NULL),left(NULL),right(NULL),parent(p),count(0){};
	};
	void generateTree(TreeNode* node){
		if(node->top){
			if(node->count>0){
				node->left=new TreeNode('(',node);
				node->left->count=node->count-1;
				node->left->top=node->left;
				generateTree(node->left);
				node->right=new TreeNode(')',node);
				node->right->count=node->count;
				if(node->top->parent)
					node->right->top=node->top->parent->top;
				generateTree(node->right);
			}else{
				node->right=new TreeNode(')',node);
				node->right->count=node->count;
				if(node->top->parent)
					node->right->top=node->top->parent->top;
				generateTree(node->right);
			}
		}else{
			if(node->count>0){
				node->left=new TreeNode('(',node);
				node->left->count=node->count-1;
				node->left->top=node->left;
				generateTree(node->left);
			}else{
				return;
			}
		}
	}
	void traverseTree(TreeNode* node,vector<string>& results,string upStr){
		if(!node->left&&!node->right){
			ostringstream ostr;
			ostr<<upStr;
			ostr.put(node->val);
			results.push_back(ostr.str());
			return;
		}
		if(node->left){
			ostringstream ostr;
			ostr<<upStr;
			ostr.put(node->val);
			traverseTree(node->left,results,ostr.str());
		}
		if(node->right){
			ostringstream ostr;
			ostr<<upStr;
			ostr.put(node->val);
			traverseTree(node->right,results,ostr.str());
		}
	}
    vector<string> generateParenthesis(int n) {
        vector<string> results;
		if(n==0)
			return results;
		TreeNode* head=new TreeNode('(');
		head->count=n-1;
		head->top=head;
		generateTree(head);
		traverseTree(head,results,"");
		return results;
    }
};