22. 括号生成（JS实现）

1 题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

2 思路
这道题利用树的构造方法来枚举可能的情况，在枚举的过程进行剪枝操作，每个叶子节点就是*后的有效结果。注意生成过程中，表达式中左括号的数量始终小于等于右括号

3代码
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
function node(str, left, right) {
this.val = str;
this.leftChild = null;
this.rightChild = null;
this.left = left; //还剩余左括号的数量
this.right = right; //还剩余右括号的数量
}

function traverse(treeNode, result) {
let {left, right, val} = treeNode;

if (left === 0 && right === 0) { //括号用完，推入结果
result.push(val);
return;
}

if (left === 0 && right > 0) { //左括号用完，只能加右括号
treeNode.rightChild = new node(val + ‘)’, left, right – 1);
traverse(treeNode.rightChild, result);
return;
}

if (left === right) { //当前剩余的左括号和右括号数量相等，则新括号必须为左括号
treeNode.leftChild = new node(val + ‘(‘, left – 1, right);
traverse(treeNode.leftChild, result);
return;
}

if (left < right) { //其余情况既可以添加左括号，又可以添加右括号
treeNode.leftChild = new node(val + ‘(‘, left – 1, right);
traverse(treeNode.leftChild, result);
treeNode.rightChild = new node(val + ‘)’, left, right -1);
traverse(treeNode.rightChild, result);
}
}

const root = new node(‘(‘, n-1, n);
const result = [];
traverse(root, result);
return result;
};