# 26.树的子结构

## 一、 题目

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:

***给定的树 A:***

```
      3
     / \
    4   5
   / \
  1   2
```

***给定的树 B：***

```
    4
   /
  1
```

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

***示例 1：***

* 输入：A = \[1,2,3], B = \[3,1]
* 输出：false

***示例 2：***

* 输入：A = \[3,4,5,1,2], B = \[4,1]
* 输出：true

***限制：***

0 <= 节点个数 <= 10000

来源：力扣（LeetCode）

链接：<https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof>

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 二、 分析

### 拆分为两个步骤

* 在 `A树` 中找到和 `B树` 的跟节点值一样的 `R`
* 判断 `A树` 中以 `R` 为根节点的子树是不是包含和 `B树` 一样的结构

### 成立条件

满足下面任意一条

* 条件一：`B树` 是 `A树`的左树的子树
* 条件二：`B树` 是 `A树`的右树的子树
  * 上面这两个条件明显可以递归了
* 条件三：`A树` 某节点为`根节点`的树包含 `B树`
  * 这个看来需要辅助函数

> 伪代码： `return (三 || 一 || 二)`

## 三、 代码

```swift
func isSubStructure(_ A: TreeNode?, _ B: TreeNode?) -> Bool {
    guard let treeA = A, let treeB = B else { return false }
    return (isContain(A, treeB) || isSubStructure(treeA.left, treeB) || isSubStructure(treeA.right, treeB))
}
```

***完成\*\*\*\* ****`条件三`**** \*\*\*\*的辅助函数：***

```swift
func isContain(_ A: TreeNode?, _ B: TreeNode?) -> Bool {
    if B == nil {
        return true // B遍历完了 不论A还有没有 A已经包含了A了
    }
    if A == nil {
        return false // A遍历完了 B还有 肯定不包含
    }

    guard let treeA = A, let treeB = B, treeA.val == treeB.val else { return false }

    return isContain(treeA.left, treeB.left) && isContain(treeA.right, treeB.right)
}
```

![1](/files/-MgpMn3OwDsm_xeTwgpx)

### 复杂度分析

***时间复杂度O(MN)：***&#x5176;中 M N 分别为 A B 树的节点个数。

***空间复杂度O(M)：***


---

# 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://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/26.-shu-de-zi-jie-gou.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.