331. 验证二叉树的前序序列化

题目

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #

题解

栈

我们可以定义一个概念，叫做槽位。一个槽位可以被看作「当前二叉树中正在等待被节点填充」的那些位置。

二叉树的建立也伴随着槽位数量的变化。每当遇到一个节点时：

• 如果遇到了空节点，则要消耗一个槽位；
• 如果遇到了非空节点，则除了消耗一个槽位外，还要再补充两个槽位。

/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function(preorder) {
  let n = preorder.length;
  let slot = 1; // 初始有一个槽位
  let i = 0;
  while (i < n) {
    if (slot === 0) return false;
    if (preorder[i] === ",") i++;
    else if (preorder[i] === "#") {
      slot--;
      i++;
    } else {
      while (i < n && preorder[i] !== ",") {
        i++;
      }
      slot++;
    }
  }
  return slot === 0;
};