题解 | #牛圈围栏问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串一维数组
     */
    public static ArrayList<String> strings = new ArrayList<>();
    public String[] generateParenthesis (int n) {
        // write code here
        search(0,0,n,new StringBuffer());
        System.out.println(strings);
        String[] string_arr = new String[strings.size()];
        for(int i=0;i<string_arr.length;i++){
            string_arr[i]= strings.get(i);
        }
        return string_arr;
    }

    public void search(int left_cur,int right_cur,int n,StringBuffer stringBuffer){
        if(right_cur > left_cur|| left_cur>n){
            return;
        }
        if(left_cur==n && right_cur==n){
            strings.add(stringBuffer.toString());
            return;
        }
        stringBuffer.append('(');
        search(left_cur+1,right_cur,n,stringBuffer);
        stringBuffer.deleteCharAt(stringBuffer.toString().length()-1);
        stringBuffer.append(')');
        search(left_cur,right_cur+1,n,stringBuffer);
        stringBuffer.deleteCharAt(stringBuffer.toString().length()-1);
    }

}

本题的知识点考察的是二叉树的建立，可以将题目理解成一棵二叉树，每个分支节点的左节点为‘（’，分支节点的右节点为‘）’，结束条件是路径上的左括号或者有括号个数等于n,而且树延伸必须满足‘（’数目大于等于‘）’个数