# 判断是否子树|博客系列

> 本文介绍如何判断一棵二叉树是否为另一棵二叉树的子结构，包含题目描述、解题思路、二叉树节点结构定义及详细的 JavaScript 实现代码，适合数据结构与算法学习者参考。

- 原文：https://feinterview.poetries.top/docs/fe-blog-docs/blog-docs/data-struct/9-%E5%88%A4%E6%96%AD%E6%98%AF%E5%90%A6%E5%AD%90%E6%A0%91
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2025.10.25

---

## 判断是否子树📕

### 题目描述

输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。

树的节点结构为:

```javascript
/*
* 二叉树结点类
*/
class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
```

如下图, `tree2`为`tree1`的子结构

![img9](https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/binaryTree9.png)

### 解题思路

假设需要判断的两颗树为`tree1`和`tree2`,需要判断`tree2`是否是`tree1`的子结构:

1. 若`tree2`是`tree1`的子结构,那么`tree2`的根节点必定为`tree1`中的某个节点, 所以要先找出这个节点;
2. 在`tree1`中找到了这个节点后, 再判断这个节点下的所有子节点是否和`tree2`的子节点相同.

### coding

```javascript
/*
* @param {Node} 节点1
* @param {Node} 节点2
* @return {Boolean} 树2是否是树1的子结构
*/
function isSubTree(node1, node2) {
    let result = false
    if (node1 && node2) {
        if (node1.value === node2.value) { // 若是节点的值相同
            result = doesNode1HasNode2(node1, node2) // 判断后面的子节点结构是否相同
        }
        if (!result) { // 若是根节点的值不同, 则用树1的左子树遍历
            result = isSubTree(node1.left, node2)
        }
        if (!result) { // 用树1的右子树遍历
            result = isSubTree(node1.right, node2)
        }
    }
    return result
}
/*
* node2是否是node1的子树: node1和node2的根节点的值是否相同
* @param {Node} 节点1
* @param {Node} 节点2
* @return {Boolean} 树2是否是树1的子结构
*/
function doesNode1HasNode2(node1, node2) {
    if (!node2) { // 若是node2全遍历完了则说明node1包含node2
        return true
    }
    // 若是node1遍历完了 或者 两个节点的值不相同
    if (!node1 || node1.value !== node2.value) {
        return false
    }
    // 节点的左子树和右子树都得相同
    return (
        doesNode1HasNode2(node1.left, node2.left) &&
        doesNode1HasNode2(node1.right, node2.right)
    )
}
const tree1 = new Node(0, new Node(1, new Node(3)), new Node(2));
const tree2 = new Node(1, new Node(3));
console.log(isSubTree(tree1, tree2));
```
