For the following two trees:
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 = True return serialized_tree traverse(s) return exists
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.