Leecode Generate Parentheses in Java

題目：

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:

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

這個題目如果是問個數的話，那就是Catalan Number的一種了

不過這一題沒那麼簡單，是要你把所有的Pattern都生出來

簡單的畫一下Recursion tree就大概知道了

左括號的數目一定要 >=右括號的數目

重點應該是在於，我怎麼要讓程式自動在一個左括號之後

能夠自動去選擇我下一個要是左括，或者是右括號

這樣才能生成所有想要的結果。


所以在這裡會有分歧點

需要一個if來判斷現在是左括號還有quota可以用

另一個if來判斷現在是不是還有右括號，而且右括號數目比左括號多

這兩種狀況就能涵蓋所有的結果

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        
    if(nums==null)
        return null;
        
    if(nums.length==1)
        return new TreeNode(nums[0]);
    
    TreeNode node = BuildTree(0,nums.length-1,nums);
    return node;

    }
    
    TreeNode BuildTree(int start,int end, int[]nums){
        
        if(start>end)
            return null;
        
        int mid=(start+end)/2;
        TreeNode node=new TreeNode(nums[mid]);
        
        node.left=BuildTree(start,mid-1,nums);
        node.right=BuildTree(mid+1,end,nums);
        
        return node;
     }
    
    
}