LintCode 245 [Subtree]

原题

有两个不同大小的二进制树： T1 有上百万的节点； T2 有好几百的节点。请设计一种算法，判定 T2 是否为 T1的子树。

样例
下面的例子中 T2 是 T1 的子树：

       1                3
      / \              / 
T1 = 2   3      T2 =  4
        /
       4

下面的例子中 T2 不是 T1 的子树：

       1               3
      / \               \
T1 = 2   3       T2 =    4
        /
       4

解题思路

• 写一个前序遍历，将二叉树扁平化为string
• 判断string1是不是string2的子串

完整代码

"""
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
        res = []
        self.get(T1, res)
        s1 = "".join(res)
        
        res = []
        self.get(T2, res)
        s2 = "".join(res)
        
        return s2 in s1
        
    def get(self, root, res):
        if root is None:
            res.append("#")
            return 
        res.append(str(root.val))
        self.get(root.left, res)
        self.get(root.right, res)