> For the complete documentation index, see [llms.txt](https://ryukiedev.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/26.-shu-de-zi-jie-gou.md).

# 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)：***