1. 题目

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

例如：
image.png

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

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

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

给出的输入格式一定是有效的，它永远不会包含两个连续的逗号，比如："1,,3"

要求：不允许重建树

示例1：

  1. 输入：preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
  2. 输出：true

方法1：栈

  1.    func isValidSerialization(str : String) -> Bool {
  3.         var stack = [String.SubSequence]()
  4.         let arr = str.split(separator: ",")
  5.         for item in arr  {
  6.             print("\(item)")
  7.             stack.append(item)
  8.             while (stack.count >= 3 && stack[stack.count-1] == "#" && stack[stack.count-2] == "#" && stack[stack.count-3] != "#") {
  9.                 stack.removeLast()
  10.                 stack.removeLast()
  11.                 stack.removeLast()
  12.                 stack.append("#")
  13.             }
  16.         }
  17.         return stack.count == 1 && stack.first == "#"
  20.     }

链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/solution/pai-an-jiao-jue-de-liang-chong-jie-fa-zh-66nt/
来源：力扣（LeetCode）