Shortest+simplest Python


  • 30

    The "proper" way:

    def isSameTree(self, p, q):
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        return p is q
    

    The "tupleify" way:

    def isSameTree(self, p, q):
        def t(n):
            return n and (n.val, t(n.left), t(n.right))
        return t(p) == t(q)
    

    The first way as one-liner:

    def isSameTree(self, p, q):
        return p and q and p.val == q.val and all(map(self.isSameTree, (p.left, p.right), (q.left, q.right))) or p is q

  • 0
    S

    Hi, thanks for your sharing! I am wondering what it means when comparing two treenodes by '=='? I try to create two instances of class TreeNode and compare them by '==', and then the results always are False.


  • 1

    It's True if both are the same TreeNode instance (can't happen there, as p and q must have failed to get there) or if both are None (that's what I'm using it for).


  • 0
    S

    Thanks, man! Now I understand it!


  • 0
    C

    hi i am a beginner, could u please tell me what is the meaning of (if p and q: )? thank you very much


  • 1

    @crazystonesss That tests whether both p and q are true (i.e., actual nodes, not None).


  • 0
    Q
    This post is deleted!

  • 2
    O

    @StefanPochmann The tuple expansion one is awesome! Just nitpicking: I think "p is q" is more proper here.

    "p == q" works here because given the TreeNode implementation it falls back to, I believe, object.__eq__ which happens to compare the references instead of the contents, while using "p is q" clearly specifies our intention of doing reference comparison. I always prefer specificity over implementation-dependent usage. : )

    Well, here is an equivalent 1-liner:

    class Solution(object):
        def isSameTree(self, p, q):
            return p is q or bool(p and q) and p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
    

  • 1

    @o_sharp Yes, definitely should be is. Thanks, fixed. I looked through my old submissions, initially I did use is, then wrote the tuple solution, and then when going back to the normal way, apparently I forgot to change == back to is.

    Two more one-liners:

    def isSameTree(self, p, q):
        return p and q and p.val == q.val and all(map(self.isSameTree, (p.left, p.right), (q.left, q.right))) or p is q
    
    def isSameTree(self, p, q):
        return p and q and p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) or p is q
    

    Note that I put p is q at the end, so I don't need the bool() around p and q. I think the only downside should be that comparing a tree with itself is slower, but that seems like an odd thing to do. Actually I had the first one (just with ==) back then already, don't know why I didn't post it. Maybe I didn't like the line being so long or maybe I really wanted it to be the "simplest"...


  • 0
    D

    @o_sharp Hi, can you explain further why we need to use "p is q" rather than "p == q" here? Why doing reference comparison? Thank you.


  • 2
    O

    @dcsds1 p is q means if p and q are the same object. With c implementation in mind, they should point to the same address.

    p == q is equivalent to p.__eq__(q), which really depends on how the class is implemented. By default, __eq__ also compares addresses.


  • 0
    T

    I can't write the shortest Python code...
    fail...


Log in to reply
 

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