10/26/2020

[LeetCode] 331. Verify Preorder Serialization of a Binary Tree

 Problem : https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

Re-create node list by splitting the input string with comma.

Then iterate the node list with pre-order traversal process.

Validate the tree node during traversal.


class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        nodes = preorder.split(',')
        
        if not nodes : return True
        
        def helper(i):
            if i >= len(nodes):
                return (i, False)
            
            if nodes[i] == '#':
                return (i, True)
            
            i, result = helper(i+1)
            if not result:
                return (i, False)
            
            i, result = helper(i+1)
            if not result:
                return (i, False)
            
            return (i, True)
        
        i, result = helper(0)
        
        return i == len(nodes) - 1 and result

No comments:

Post a Comment