子树

https://www.lintcode.com/problem/245/solution?utm_source=sc-libao-ql

描述

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

若 T1 中存在从节点 n 开始的子树与 T2 相同，我们称 T2 是 T1 的子树。也就是说，如果在 T1 节点 n 处将树砍断，砍断的部分将与 T2 完全相同。

样例

样例 1：

输入：{1,2,3,#,#,4},{3,4}输出：true解释：下面的例子中 T2 是 T1 的子树：           1                3          / \              /     T1 = 2   3      T2 =  4            /           4

样例 2：

输入：{1,2,3,#,#,4},{3,#,4}输出：false解释：下面的例子中 T2 不是 T1 的子树：           1               3          / \               \    T1 = 2   3       T2 =    4            /           4

分析：

2个递归，一个判断是否相同树，一个判断是否是子树。

是否是子树的情况包含相同，或者在左右子树。

```python
from lintcode import (
    TreeNode,
)

"""
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 is_subtree(self, t1: TreeNode, t2: TreeNode) -> bool:
        # write your code here
        if not t2:
            return True

        if not t1:
            return False

        if self.is_same_tree(t1,t2):
            return True           

        return self.is_subtree(t1.left,t2) or self.is_subtree(t1.right, t2)
    
    def is_same_tree(self, t1: TreeNode, t2: TreeNode) -> bool:
        if not t1 and not t2:
            return True 
        if not t1 or not t2:
            return False
        if t1.val == t2.val:
            return self.is_same_tree(t1.left,t2.left) and self.is_same_tree(t1.right, t2.right)
        return False
```

用stack 不用递归的话：注意左右子树都要加入，不要用elif

``python
from lintcode import (
    TreeNode,
)

"""
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 is_subtree(self, t1: TreeNode, t2: TreeNode) -> bool:
        # write your code here
        if not t2:
            return True
        if not t1:
            return False
        stack = [t1]
        while stack:
            cur = stack.pop()
            if self.is_same_tree(cur,t2):
                return True
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return False

    
    def is_same_tree(self, t1: TreeNode, t2: TreeNode) -> bool:
        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.is_same_tree(t1.left,t2.left) and self.is_same_tree(t1.right, t2.right)
       
```