# 子树

描述

有两个不同大小的二叉树： `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)
       
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2024/zi-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.