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:
Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"Output: true
Example 2:
Input: "1,#"Output: false
Example 3:
Input: "9,#,#,1"Output: false 这个题目的思路参考, 本质上就是看这个tree 是否valid, 然后就要满足可以有的children数>= 0 , 最后== 0, 那么最开始slot = 1, 然后for loop, 每 多一个数字, 表明可以多一个child, 如果是#表明少一个child, 最后children数等于0 即可. 就是用Stack,每次碰到#, 去看stack[-1]是否为#, 如果是的话表明stack[-2]的children满了, 所以将stack.pop()执行两次, 并且循环, 然后把#放到stack里面, 这里在stack.pop()两次 的中间, 加入一个stack 非空的判断, 是针对"##" "###"这样的情况来的.最后len(stack) == 1 and stack[-1] == '#' Code: T: O(n) S: O(n)
1 class Solution: 2 def preorderValid(self, preorder): 3 stack, preorder = [], preorder.split(',') 4 for p in preorder: 5 while (p == '#' and stack and stack[-1] == '#'): 6 stack.pop() 7 if not stack: return False 8 stack.pop() 9 stack.append(p)10 return len(stack) == 1 and stack[-1] == '#'
Code: T: O(n) S: O(1)
class Solution: def preorderValid(self, preorder): slot, preorder = 1, preorder.split(',') for p in preorder: if slot == 0: return False # means that should have no children anymore if p == '#': slot -= 1 else: slot += 1 return slot == 0