原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv33m7/

解法一:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        def(res,n,n,"");
        return res;
    }

    private void def(List<String> list,int left,int right,String cur) {
        if (left == 0 && right == 0) {
            list.add(cur);
            return;
        }
        if (left < 0) {
            return;
        }
        if (right < left) {
            return;
        }
        def(list,left-1,right,cur + "(");
        def(list,left,right-1,cur + ")");

    }
}

思路：

• 1，括号组合中左括号的数量等于右括号的数量
• 2，括号组合中任何位置左括号的数量都是大于等于右括号的数量

第一条很容易理解，我们来看第二条，比如有效括号"(())()"，在任何一个位置右括号的数量都不大于左括号的数量，所以他是有效的。如果像这样"())()"第3个位置的是右括号，那么他前面只有一个左括号，而他和他前面的右括号有2个，所以无论如何都不能组合成有效的括号。

所以总的来说就是前序遍历，需要注意第一点的是递归返回的条件。

前序遍历代码：

public static void preOrder(TreeNode tree) {
    if (tree == null)
        return;
    System.out.printf(tree.val + "");
    preOrder(tree.left);
    preOrder(tree.right);
}