[Swift]LeetCode331.验证二叉树的前序序列化|VerifyPreorderSerializationofaBinaryTr ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10261941.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

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

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:

Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

Example 2:

Input: "1,#"
Output: false

Example 3:

Input: "9,#,#,1"
Output: false

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

     _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

72ms

 1 class Solution {
 2     func isValidSerialization(_ preorder: String) -> Bool {
 3         let set = CharacterSet(charactersIn: ",")
 4         let preorderArr = preorder.components(separatedBy: set)
 5         
 6         if preorderArr.count % 2 == 0 {
 7             return false
 8         }
 9         
10         var i = 1
11         
12         for c in preorderArr {
13             if i == 0 {
14                 return false
15             }
16             if c == "#" {
17                  i -= 1
18             }else {
19                 i += 1
20             }
21         }
22         
23         return i == 0
24     }
25 }

76ms

 1 class Solution {
 2     func isValidSerialization(_ preorder: String) -> Bool {
 3         let arr = preorder.components(separatedBy:",")
 4         if arr[0] == "#" && arr.count != 1 {
 5             return false
 6         }
 7         var count = 0
 8         
 9         for i in 0..<arr.count {
10             let str = arr[i]
11             
12             if str == "#" {
13                 count += 1
14             } else {
15                 count -= 1
16             }
17             
18             if count == 1 && i != arr.count - 1 {
19                 return false
20             }
21         }
22         
23         return count == 1
24     }
25 }

80ms

 1 class Solution {
 2     func isValidSerialization(_ preorder: String) -> Bool {
 3  let nodes = preorder.components(separatedBy: ",")
 4         var stack = [String]()
 5         
 6         for i in 0..<nodes.count {
 7             let node = nodes[i]
 8             while node == "#" && !stack.isEmpty && stack.last! == "#" {
 9                 stack.removeLast()
10                 if stack.isEmpty {
11                     return false
12                 }
13                 stack.removeLast()
14             }
15             stack.append(node)
16         }
17         
18         return stack.count == 1 && stack.last! == "#"
19     }
20 }

140ms

 1 class Solution {
 2     func isValidSerialization(_ preorder: String) -> Bool {
 3         let res = preorder.components(separatedBy: ",")
 4         var diff = 1
 5         
 6         for r in res {
 7             diff -= 1
 8             if diff < 0 {
 9                 return false
10             }
11             if r != "#" {
12                 diff += 2
13             }
14         }
15         
16         return diff == 0
17     }
18 }