0331-验证二叉树的前序序列化.md

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

 _9_
/   \

3 2 / \ /
4 1 # 6 / \ / \ / \

# # # #

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

示例 1:

输入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 输出: true 示例 2:

输入: "1,#" 输出: false 示例 3:

输入: "9,#,#,1" 输出: false

var isValidSerialization = function(preorder) {
  preorder = preorder.split(',')
  const stack = []
  let i = 0
  while(i < preorder.length) {
    const cur = preorder[i]
    if (cur === '#' && stack[stack.length - 1] === '#' && stack[0] !== '#') {
      stack.pop()
      stack.pop()
      stack.push('#')
      while(stack.length > 1 && stack[stack.length - 1] === '#' && stack[stack.length - 2] === '#') {
        stack.pop()
        stack.pop()
        stack.pop()
        stack.push('#')
      }
    } else {
      stack.push(cur)
    }
    i++
  }
  return stack.length === 1 && stack[0] === '#'
};

解题思路: 当遇到当前字符串为#并且栈顶也为#的时候，就需要删除叶子节点与两个##，并推入一个#代表该节点已经完结，若栈内还有满足栈顶和栈顶下一位依旧等于#，则循环处理掉叶子节点，记得要处理根节点被过早的处理成为#的异常情况，最后返回栈的长度为1且栈内唯一元素为#即可