Python solution with detailed explanation


  • 0
    G

    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/

    Stack Simulation

    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
    

Log in to reply
 

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