# 245.Subtree

## 1.Description(Easy)

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`.

### Notice

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

**Example**

T2 is a subtree of T1 in the following case:

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

T2 isn't a subtree of T1 in the following case:

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

## 2.Code

判断 T2是否是 T1的子树，首先应该在 T1中找到 T2的根节点，找到根节点后两棵子树必须完全相同。所以整个思路分为两步走：找根节点，判断两棵树是否全等。咋看起来极其简单，但实际实现中还是比较精妙的，尤其是递归的先后顺序及条件与条件或的处理

```
public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) return true;
        if (T1 == null) return false;
        //注意这里是T1,T2的equal比较，然后递归left和right
        return isEqual(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
    }

    public boolean isEqual(TreeNode T1, TreeNode T2) {
        if (T1 == null && T2 == null) return true;
        if (T1 == null || T2 == null) return false;
        if (T1.val != T2.val) return false;
        return isEqual(T1.left, T2.left) && isEqual (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://junnie.gitbook.io/nine-chapter/2.binary-tree/245subtree.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.