331. Verify Preorder Serialization of a Binary Tree
- Total Accepted: 23475
- Total Submissions: 68739
- Difficulty: Medium
- Contributors: Admin
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:"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:"1,#"
Return false
Example 3:"9,#,#,1"
Return false
Code
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
if not str:
return True
diff = 1
for n in preorder.split(','):
diff -= 1
if diff < 0:
return False
if n != '#':
diff += 2
return diff == 0
Idea
Calculate the difference between in-degree and out-degree. See https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution
Code
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
if not preorder:
return True
stk = []
nodes = preorder.split(',')
for n in nodes:
while stk and stk[-1] == '#' and n == '#':
stk.pop()
if not stk:
return False
stk.pop()
stk.append(n)
return len(stk) == 1 and stk[0] == '#'
Idea
When you see two consecutive “#” characters (one on the top of stack and the other as the current node `n`), that means a subtree with two leaves has been scanned. Pop the subtree’s root as well as the ‘#’ on the stack and replace the topmost element on the stack with “#”.
See https://discuss.leetcode.com/topic/35977/simple-python-solution-using-stack-with-explanation and https://discuss.leetcode.com/topic/35973/java-intuitive-22ms-solution-with-stack