题目描述：

LeetCode 331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-oder 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:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

题目大意：

先序遍历是序列化二叉树的方式之一。当遇到非空节点时，记录节点的值。如果是空节点，我们将其记为#。

例如，题目描述中的样例二叉树可以序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中#代表空节点。

给定一个逗号分隔值字符串，校验其是否是一个正确的二叉树先序遍历序列化字符串。设计一个不需要重建树的算法。

每一个逗号分隔值字符串中的值或者是整数，或者是字符'#'，代表空节点。

你可以假设输入格式总是有效的，例如，不可能出现两个连续的逗号，比如"1,,3"。

测试用例如题目描述。

解题思路：

解法I 利用栈（Stack）数据结构

将元素压入栈

如果当前栈的深度≥3，并且最顶端两个元素为'#', '#'，而第三个元素不为'#'，则将这三个元素弹出栈顶，然后向栈中压入一个'#'，重复此过程

最后判断栈中剩余元素是否只有一个'#'

Python代码：

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        stack = collections.deque()
        for item in preorder.split(','):
            stack.append(item)
            while len(stack) >= 3 and \
                  stack[-1] == stack[-2] == '#' and \
                  stack[-3] != '#':
                stack.pop(), stack.pop(), stack.pop()
                stack.append('#')
        return len(stack) == 1 and stack[0] == '#'

解法II 统计树的出度（out-degree）和入度（in-degree）

参考链接：https://leetcode.com/discuss/83824/7-lines-easy-java-solution

在二叉树中，如果我们将空节点视为叶子节点，那么除根节点外的非空节点（分支节点）提供2个出度和1个入度（2个孩子和1个父亲）

所有的空节点提供0个出度和1个入度（0个孩子和1个父亲）

假如我们尝试重建这棵树。在构建的过程中，记录出度与入度之差，记为diff = outdegree - indegree

当遍历节点时，我们令diff - 1（因为节点提供了一个入度）。如果节点非空，再令diff + 2（因为节点提供了2个出度）

如果序列化是正确的，那么diff在任何时刻都不会小于0，并且最终结果等于0

对该算法的一个朴素理解（2016-06-08增补）：

如果在遍历过程中的某时刻，系统的入度>出度，则说明当前序列中出现过的所有分支节点的“空闲分支”均已用完，后序节点没有办法挂载到之前出现的节点之上，从而判定先序遍历的序列是不合法的。

Python代码：

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        diff = 1
        for item in preorder.split(','):
            diff -=1
            if diff < 0: return False
            if item != '#': diff += 2
        return diff == 0

另附递归重建树的解法（Time Limit Exceeded），详见代码。

Python代码：

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        items = preorder.split(',')
        map = dict()
        def isValid(start, end):
            size = end - start + 1
            if size == 0:
                return False
            if items[start] == '#':
                return size == 1
            if size == 3:
                return items[start + 1] == items[start + 2] == '#'
            for k in range(2, size):
                left, right = (start + 1, start + k - 1), (start + k, end)
                vl = map.get(left)
                if vl is None:
                    vl = map[left] = isValid(*left)
                vr = map.get(right)
                if vr is None:
                    vr = map[right] = isValid(*right)
                if vl and vr:
                    return True
            return False
        return isValid(0, len(items) - 1)

 

本文链接：http://bookshadow.com/weblog/2016/02/01/leetcode-verify-preorder-serialization-binary-tree/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码