1.题目

2.常规的遍历

对于这种要找到所有符合情况的，先明白二叉树是咋样的（树高为2n，因为n为括号对数，一对有左右两个括号），再进行剪枝获得满足要求的情况：

遍历上面二叉树的代码如下：

class Solution {
private:
    vector<string>ans;
public:
    vector<string> generateParenthesis(int n) {
        dfs(n,"");
        return ans;
    }
    void dfs(int n,string path){
        if(path.size()==2*n){//遍历到叶结点
            ans.push_back(path);
            return;
        }
        dfs(n,path+"(");
        dfs(n,path+")");
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

显然上面找出了很多不满足要求的：

["((((((","((((()","(((()(","(((())","((()((","((()()","((())(","((()))","(()(((","(()(()","(()()(","(()())","(())((","(())()","(()))(","(())))","()((((","()((()","()(()(","()(())","()()((","()()()","()())(","()()))","())(((","())(()","())()(","())())","()))((","()))()","())))(","()))))",")(((((",")(((()",")((()(",")((())",")(()((",")(()()",")(())(",")(()))",")()(((",")()(()",")()()(",")()())",")())((",")())()",")()))(",")())))","))((((","))((()","))(()(","))(())","))()((","))()()","))())(","))()))",")))(((",")))(()",")))()(",")))())","))))((","))))()",")))))(","))))))"]

  

 

  
1
 

而我们要的是：

["((()))","(()())","(())()","()(())","()()()"]

  

 

  
1
 

常规遍历理解后，就是剪枝处理：

3.剪枝处理

（1）右括号close数量大于左括号open时不符合
（2）左括号或者右括号数量大于n时不符合
需要判断左括号数和右括号数，所以递归函数要传参open和close括号数值。

class Solution {
private:
    vector<string>ans;
public:
    vector<string> generateParenthesis(int n) {
        dfs(n,"",0,0);
        return ans;
    }
    void dfs(int n,string path,int open,int close){
        if(open>n || close>n || close>open){
            return;
        }
        if(path.size()==2*n){//遍历到叶结点
            ans.push_back(path);
            return;
        }
        dfs(n,path+"(",open+1,close);
        dfs(n,path+")",open,close+1);
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

4.根据条件判断是否遍历

进入左子树的资格： open<n
进入右子树的资格：close<open（右括号比左括号多就没法玩了）
上面的判定条件还是要举例画出二叉树判断下才知道。

class Solution {
private:
    vector<string>ans;
public:
    vector<string> generateParenthesis(int n) {
        dfs(n,"",0,0);
        return ans;
    }
    void dfs(int n,string path,int open,int close){
        if(path.size()==2*n){//遍历到叶结点
            ans.push_back(path);
            return;
        }
        if(open<n  && close<=n){
            dfs(n,path+"(",open+1,close);//左子树
        }
        if(close<open && close<=n && open<=n){
            dfs(n,path+")",open,close+1);//右子树
        }
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

5.其他写法

如果path不用上面的写法，可以用push和pop写法（不要漏了pop）：

class Solution {
private:
    vector<string>ans;
public:
    vector<string> generateParenthesis(int n) {
        dfs(n,"",0,0);
        return ans;
    }
    void dfs(int n,string path,int open,int close){
        if(path.size()==2*n){//遍历到叶结点
            ans.push_back(path);
            return;
        }
        if(open<n  && close<=n){
            path.push_back('(');
            dfs(n,path,open+1,close);//左子树
            path.pop_back();
        }
        if(close<open && close<=n && open<=n){
            path.push_back(')');
            dfs(n,path,open,close+1);//右子树
            path.pop_back();
        }
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/115624425