Sub Tree

Question

You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Thoughts

recursive解决

Solution

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    # @param T1, T2: The roots of binary tree.
    # @return: True if T2 is a subtree of T1, or false.
    def isSubtree(self, T1, T2):
        # write your code here
        if not T2:
            return True
        if not T1:
            return False
        return self.isSameTree(T1, T2) or self.isSubtree(T1.left, T2) or self.isSubtree(T1.right, T2)

    def isSameTree(self, t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        if t1.val != t2.val:
            return False
        return self.isSameTree(t1.left, t2.left) and self.isSameTree(t1.right, t2.right)