Leetcode 331: Verify Preorder Serialization of a Binary Tree

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

Leave a comment

Your email address will not be published. Required fields are marked *