LeetCode题解：22. 括号生成，BFS，JavaScript，详细注释

[chencl1986]

原题连接：https://leetcode-cn.com/problems/generate-parentheses/

解题思路：

1. 假设随意生成括号，最终的字符串长度为2*n，也就是每个位置都有左右括号两种可能性，如果将逐个生成的过程展开，会类似一个二叉树的形式。
2. 那么可以模拟使用BFS层序遍历二叉树的方法，同时按照以下规则过滤掉无效括号：
   • 有效括号的左右括号数量都必须为n
   • 第一个括号必须是左括号
3. 为了高效地统计括号数量，可以将生成的括号及其数量存储在一个节点中。

// 使用一个节点表示当前已生成的括号，以及左右括号的数量
function Node(val = '', left = 0, right = 0) {
  this.val = val;
  this.left = left;
  this.right = right;
}
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  let result = []; // 存储结果
  // 使用队列，模拟二叉树的层序遍历过程，初始状态有一个左括号，模拟根节点
  // 由于要求是成对括号，第一个括号必然为左括号，同时左括号计数为1
  let queue = [new Node('(', 1)];

  // 队列中保存的是每一层括号的分布情况
  while (queue.length) {
    // 缓存队列长度，使每次for循环都只出队当前一层的元素
    const queueLength = queue.length;

    // 将当前层的元素依次出队
    for (let i = 0; i < queueLength; i++) {
      const node = queue.shift();

      // 对于每一个节点，下一次生成的括号都有两种情况
      // 由于初始状态已经固定了第一个括号为左括号
      // 之后只要保证最终生成的左右括号分别为n个即可
      // 由于括号是成对生成的，最终生成的左括号数量必须小于n
      if (node.left < n) {
        queue.push(new Node(node.val + '(', node.left + 1, node.right));
      }
      // 只要右括号数量小于左括号，自然就保证了右括号小于n个
      if (node.left > node.right) {
        // 生成一个新节点
        const newNode = new Node(node.val + ')', node.left, node.right + 1);

        // 由于最后一个括号一定是右括号，如果当前右括号的数量已经到达n
        // 代表括号已经生成完毕，直接将当前节点的值存入result即可
        if (newNode.right === n) {
          result.push(newNode.val);
        } else {
          // 括号还未生成完毕，将节点存入队列，用于下一次括号生成
          queue.push(newNode);
        }
      }
    }
  }

  return result;
};