LeetCode 331. Verify Preorder Serialization of a Binary Tree
由 瞳人
发布于 March 14, 2017, 4:10 p.m.
3 个评论
题目
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），还集中于两种解法：一种利用树结点的出度等于入度（如 dietpepsi，JazzBro），另一种利用如题中定义的正确的树不能再插入多余结点（如 hohomi，Dragon.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 |
1234 April 6, 2017, 5:21 p.m. | Reply
test
3 Comments