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