lintcode 245. 子树

难度：简单

1. Description

image.png

2. Solution

原理：前序遍历相同的完全二叉树，是完全相同的二叉树。
把T1、T2按照完全二叉树来做前序遍历（空节点用'#'表示）。

• python

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param T1: The roots of binary tree T1.
    @param T2: The roots of binary tree T2.
    @return: True if T2 is a subtree of T1, or false.
    """
    def pre_order(self, root, rst):
        if root is None:
            rst.append('#')
            return 
        rst.append(str(root.val))
        self.pre_order(root.left, rst)
        self.pre_order(root.right, rst)
        
    def isSubtree(self, T1, T2):
        # write your code here
        rst = []
        self.pre_order(T1, rst)
        po1 = ','.join(rst)
        
        rst = []
        self.pre_order(T2, rst)
        po2 = ','.join(rst)
        
        return po1.find(po2)!=-1

3. Reference

1. (https://www.lintcode.com/problem/subtree/description?_from=ladder&&fromId=6)[https://www.lintcode.com/problem/subtree/description?_from=ladder&&fromId=6]