LeetCode之Generate Parentheses（C++）
LeetCode之Generate Parentheses（C++）
forrestlin
发布于 2018-05-24 11:25:40
发布于 2018-05-24 11:25:40
题目：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;
}
};笔者认为数据结构设计的有些冗余，而且两次使用递归（生成括号和遍历括号树），希望各位技术大牛加以指正，万分感谢。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年10月27日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读