LeetCode 331. Verify Preorder Serialization of a Binary Tree

瞳人


发布于 March 14, 2017, 4:10 p.m.

2 个评论

Algorithm LeetCode


题目

331. Verify Preorder Serialization of a Binary Tree

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 #.

1
2
3
4
5
6
7
     _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

解法

看到该题目的标签中有 stack,然后就很自然的想到了用类似中序遍历的压栈弹栈方式来遍历该字符串。

1
2
3
4
5
preorder = "...,a,#,x"
stack                                   stack
| |                                      | |
|#| <- top is #. We have finished a's    | |
|a| left subtree, so pop # a and push x  |x|

当过程中发现栈不够弹,则返回 False。在遍历结束后,若栈只有一个元素 #,则返回 True,否则返回 False。题目中的例子演示为:

1
2
3
4
5
| |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |
| | 9 | | 3 | | 4 | | # |#| # | | 1 | | # | | # | | 2 | | # | | 6 | | # | | # | |
| |-->| |-->| |-->|4|-->|4|-->|#|-->| |-->|#|-->| |-->| |-->| |-->| |-->| |-->| |
| |   | |   |3|   |3|   |3|   |3|   |1|   |1|   |#|   | |   |#|   | |   |#|   | |
| |   |9|   |9|   |9|   |9|   |9|   |9|   |9|   |9|   |2|   |2|   |6|   |6|   |#|

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def isValidSerialization(self, preorder):
    if not preorder:
        return False
    stack = []
    for c in preorder.split(','):
        if len(stack) > 0:
            top = stack[-1]
            if top == '#':
                if len(stack) < 2:
                    return False
                else:
                    del stack[-2:]
        stack.append(c)

    if len(stack) == 1 and stack[-1] == '#':
        return True
    else:
        return False

然后习惯性地学习一下讨论区,发现除了类似上述解法之外(如 harshaneel),还集中于两种解法:一种利用树结点的出度等于入度(如 dietpepsiJazzBro),另一种利用如题中定义的正确的树不能再插入多余结点(如 hohomiDragon.PW)。其实这两种思想的本质是一致的,出度减去入度就是还能插入的结点数目。

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def isValidSerialization(self, preorder):
    if not preorder:
        return False
    slot = 1
    for c in preorder.split(','):
        if slot == 0:
            return False

        if c == '#':
            slot -= 1
        else:
            slot += 1

    return slot == 0

哎呦, 不错哦!

2 Comments

1234 April 6, 2017, 5:21 p.m. | Reply

test

test April 6, 2017, 5:25 p.m. | Reply

test


Leave a Comment:

博客搜索

友情链接

公告

本博客代码已经公布在 Github 上,欢迎交流指正。

QQ 邮箱对 mailgun 不太友好, 所以使用 QQ 邮箱的评论, 可能会无法及时收到邮件。我会尽快寻找其他解决方案的。

本人现在独自使用 linode vps, 20 美元/月, 感觉压力大, 如果有意一起合租, 可以联系我. 在我的任意一篇文章下面留言即可. 关于使用方式, 现在倾向于使用 docker.