[LeetCode]Verify Preorder Serialization of a Binary Tree

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. 大睿-SCTrojan 大睿-SCTrojan 发布于 2016年2月3日 03:22 #

    我觉得第一个方法不是严格上的栈吧,毕竟栈只支持top(),这里要检查top和top的下一个以及下下一个

  2. 在线疯狂 在线疯狂 发布于 2016年2月3日 13:13 #

    是的,不是严格意义上的栈,应该把栈顶的前3个元素弹出,如果不能合并,再重新压入。

  3. 洪北七 洪北七 发布于 2016年6月8日 14:26 #

    请问第二种方法的正确性怎么理解?或者怎么证明?

  4. 在线疯狂 在线疯狂 发布于 2016年6月8日 20:42 #

    我也不会严谨的证明,一个朴素的理解:如果在遍历过程中的某时刻,系统的入度>出度,则说明当前序列中出现过的所有分支节点的“空闲分支”均已用完,后序节点没有办法挂载到之前出现的节点之上。从而判定先序遍历的序列是不合法的。

  5. 洪北七 洪北七 发布于 2016年6月10日 09:47 #

    谢谢,隐约可以理解一下。

张贴您的评论