My incorrect solution that didn't cover a case got accepted


  • 2

    For the following two trees:

    [4,1,null,null,2]
    [1,null,4,2]
    

    My code gives True but in actual fact the expected value in Python 2 is False. My code that doesn't handle this case got accepted anyway.

    EDIT: I found that in Java, the expected value is True; there is some inconsistency.

    class Solution(object):
        def isSubtree(self, s, t):
            """
            :type s: TreeNode
            :type t: TreeNode
            :rtype: bool
            """
            def serialize(node):
                if not node:
                    return '#'
                return serialize(node.left) + str(node.val) + serialize(node.right)
            serialized_t = serialize(t)
            exists = [False]
            def traverse(node):
                if not node:
                    return '#'
                serialized_tree = traverse(node.left) + str(node.val) + traverse(node.right)
                if serialized_tree == serialized_t:
                    exists[0] = True
                return serialized_tree
            traverse(s)
            return exists[0]
    

    The reason is that I used in-order traversal which does not guarantee a unique serialization of the tree.

    I have reported this missing test case.


Log in to reply
 

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