6 lines Python, 7 lines Java


  • 14

    Python

    def isValidSerialization(self, preorder):
        need = 1
        for val in preorder.split(','):
            if not need:
                return False
            need -= ' #'.find(val)
        return not need
    

    Java

    public boolean isValidSerialization(String preorder) {
        int need = 1;
        for (String val : preorder.split(",")) {
            if (need == 0)
                return false;
            need -= " #".indexOf(val);
        }
        return need == 0;
    }

  • 0
    S

    Thanks for the solution Stefan. Could u give some more hint about the rationale here? specifically, I got a feeling that the idea here is kind of similar to the one by dietpepsi https://leetcode.com/discuss/83824/7-lines-easy-java-solution, but in ur solution, the 'need' is only gets decremented, never incremented, which makes wonder how it will work. Thanks!


  • 0

    It's the same. You only missed that ' #'.find(val) and " #".indexOf(val); evaluate to -1 for numbers, so that subtracting them does increment my need.


  • 0
    S

    Apologize, I missed that, brilliant, def, one more vote from me! a couple of more questions that I wonder if u could share some insight on.

    1: the condition that 'need' will be 0 eventually. what is the best way to rationalize it? so far, my take on this is that:

    -- if we have a full balanced BT of n levels, then we must have sum(1+2+2^(n-1))=2^n-1 numeric nodes and 2^n '#' nodes => so ONE more '#' than numeric node for now

    -- from there, whenever we prune ONE numeric node to form any other new tree, we will remove two associated '#' nodes and replace the numeric node with a '#', hence effectively reduce the '#' nodes by ONE, also. => so will always be ONE more '#' than numeric node

    2: the above condition, however, is not where the real magic is while 'if (need == 0)' in the loop is, right? what is the best way rationalize this? so far, my take on this is something a bit rudimentary and inprecise:

    -- PreOrder requires that before each '#' is reached, ALL of its parent nodes has been already reached, hence at any moment, the 'need' will be positive until the when reaching last "#', where it will become 0?

    -- Haveing said that, I actually think it can be more precisely said that 'need' changes following this sequence ([init=1] -> [remains>=1] -> [@last node '#', dropto=0]) instead of what we have currently: ([init=1] -> [remains>0] -> [@last node '#', dropto=0])?

    3: from the above, how would u go about using similar logic to implement In-Order and Post-Order verification? Espeically Post-Order, I think there is a great potential, as it is almost the opposite of Pre-Order, i.e. any parent node will be reached only after ALL its children nodes are reached.

    -- so for Post-Order, if we still initialize 'need = 1', and apply the same rule of addition and subtraction, then I think it can be said that (though I couldn't wrap my head around to formalize):
    ---- 'need' changes following this sequence ([init=1] -> [dropto=-1] -> [remains<=0] ->[@last node '#', becomes=0])


  • 0

    need just tells me exactly how many "items" (actual nodes or "nulls") I still need to complete the tree. If I ever get one when I already don't need one anymore, it's false, and if I still need something at the end, it's also false.

    For post-order I'd either reverse the input and then use the exact same algorithm, or I'd start with trees = 0 and increase it for every # (it's an empty tree) and decrease it for every number (which unites two trees into one), checking that I never get down to zero and that I end up with exactly one.


  • 0
    C

    how about using need += (-1)**(val=="#") ? This expression seems more natural and easier to understand


  • 0

    @cmc I like it. Bit longer, though, and doesn't work in Java (because of the ** and the ==) and I liked using the same idea in both languages.

    Oh and I also like mine because it's tricky and unusual :-D


  • 0

    this line of Python is sooooo cool!!!
    need -= ' #'.find(val)


  • 0
    W
    This post is deleted!

Log in to reply
 

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