Solution with discussionhttps://discuss.leetcode.com/topic/80426/python-solution-with-detailed-explanation
Verify Preorder Serialization of a Binary Tree https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
- The algorithm idea can be summarized with the picture in this post: http://www.programcreek.com/2015/01/leetcode-verify-preorder-serialization-of-a-binary-tree-java/
- Same idea: https://discuss.leetcode.com/topic/35977/simple-python-solution-using-stack-with-explanation/2
- The code can be tricky to get absolutely correct. Notice all the conditions.
- Time complexity is O(N) and space complexity is O(N).
- Note - "#" will be a null tree and must return True.
class Solution(object): def isValidSerialization(self, preorder): """ :type preorder: str :rtype: bool """ st =  for x in preorder.split(","): st.append(x) while len(st) > 2 and st[-1] == "#" and st[-2] == "#": st.pop() st.pop() if st.pop() == "#": return False st.append("#") return bool(len(st)==1 and st[-1]=="#")
In-Degree and Out-Degree Concept
- In a binary tree, we can generalize the following:
- Leaf node is "#". Leaf node has in-degree 1 and out-degree = 0
- Internal node (non leaf but not root) will have in-degree 1 (just one parent) and out-degree = 2
- Root node has 0 in-degree and 2 out-degree.
- Now the invariant is that after looking at a node and incrementing in-degree, the invariant i.e, in-degree <= out_degree must be true.That is because all the potential in-degree count in the tree are solely contributed by the out-degree by the previous nodes.
- The position of that check is very critical.
class Solution(object): def isValidSerialization(self, preorder): """ :type preorder: str :rtype: bool """ preorder = preorder.split(",") in_degree, out_degree = 0, 0 for idx, x in enumerate(preorder): in_degree = in_degree + 1 if idx != 0 else in_degree if in_degree > out_degree: return False out_degree = out_degree+2 if x != "#" else out_degree return in_degree == out_degree