3 line python, using regex, easy to understand


  • 0
    S
    class Solution(object):
        def isValidSerialization(self, preorder):
            """
            :type preorder: str
            :rtype: bool
            """
            while re.search(r"\d+,#,#", preorder):
                preorder = re.sub(r"\d+,#,#", "#", preorder)
            return True if preorder == "#" else False
    

    The idea is from bottom up, keep replacing nodes with None/Nil/Null in both sides with None/Nil/Null, and eventually, a legit tree will have a None/Nil/Null left

    In other words, keep reducting "<digit>,#,#" to "#" and eventually if you get a single "#", returns true

    Example:
    "9,3,4,#,#,1,#,#,2,#,6,#,#" -> "9,3,(4,#,#),(1,#,#),2,#,(6,#,#)"
    ====>
    "9,3,#,#,2,#,#" -> "9,(3,#,#),(2,#,#)"
    ====>
    "9,#,#" -> "(9,#,#)"
    ====>
    "#"

    (Not the fastest though, beats 78% of python, and way slower than C++/Java solution)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.