专栏首页蜉蝣禅修之道LeetCode之Generate Parentheses(C++)

LeetCode之Generate Parentheses(C++)

题目: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;
    }
};

笔者认为数据结构设计的有些冗余,而且两次使用递归(生成括号和遍历括号树),希望各位技术大牛加以指正,万分感谢。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode之Intersection of two linked list不同方法

    forrestlin
  • 基于Huffman编码的压缩软件的Python实现

    forrestlin
  • LeetCode之Jump Game II

    forrestlin
  • P3372 【模板】线段树 1 线段树模版+懒惰标记

    用户2965768
  • JOJ 2676 Problem B

    题意:给三个点abc的坐标构成三角形,在三角形内部找到一点,促使a所对应的边构成的三角形占总 三角形面积的1/2,c点对应的边构成的三角形占总三角形面积的1/6...

    用户1624346
  • AVL树探秘

    一、AVL树   AVL树是一种平衡查找树,在前面的两篇文章:二叉搜索树 和 红黑树 中都提到过。由于二叉搜索树在某些特殊情况下是不平衡的(任意一个结点深度过大...

    CloudDeveloper
  • centos7配置nodejs环境

        想起自己有台显示的linux服务器,这里给博友们带来centos7发行版配置nodejs环境(这里以最新版的v8.11为例)

    十月梦想
  • 算法:跳跃表的实现

    在跳跃表中,每个节点的level数随机按1-5生成并不是很好,可以引入一个算法。在redis中,每个节点的level有1-32层。层数越大的节点越少。具体上,可...

    超级大猪
  • 性能分析之OS资源饱和度

    在做性能分析的时候,我们不可避免地判断资源到底够不够用?哪里不够?为什么不够?证据是什么?

    高楼Zee
  • 【剑指offer:两个链表的第一个公共节点】双解法

    题目提示了,空间复杂度可以降低到$O(1)$。这时候不能用哈希表,可以使用快慢指针的思路来处理。整体思路如下:

    心谭博客

扫码关注云+社区

领取腾讯云代金券