1. 题目描述

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

树的节点定义如下：

1
2
3
4
5
6
7
8
9
10
/**
 * 二叉树结点类
 */
class Node {
    constructor(value, left = null, right = null) {
        this.value = value
        this.left = left
        this.right = right
    }
}

2. 思路分析

假设判断的是p2是不是p1的子树，实现分为 2 个部分：

  1. 遍历树的函数hasSubTree：遍历 p1 的每个节点，如果当前节点的 value 和 p2 根节点的 value 相同，立即进入判断函数（下一个函数）；否则继续遍历
  2. 判断子树的函数doesTree1HaveTree2：比较当前节点的值，再递归比较 p1 和 p2 的左右节点的值

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * p2是否是p1的子树, 参数特点是: p1和p2的根节点value相同
 * @param {Node} p1
 * @param {Node} p2
 */

function doesTree1HaveTree2(p1, p2) {
    // p2遍历完了，说明p2包含在p1中
    if (!p2) {
        return true
    }

    // p1提前遍历完 || 两个节点不同, 说明p2不包含在p1中
    if (!p1 || p1.value !== p2.value) {
        return false
    }

    return doesTree1HaveTree2(p1.left, p2.left) && doesTree1HaveTree2(p1.right, p2.right)
}

/**
 * 判断p1是否包含p2
 * @param {Node} p1
 * @param {Node} p2
 */
function hasSubTree(p1, p2) {
    let result = false

    if (p1 && p2) {
        // 节点值相同, 进一步比较
        if (p1.value === p2.value) {
            result = doesTree1HaveTree2(p1, p2)
        }

        // 往左找
        if (!result) {
            result = hasSubTree(p1.left, p2)
        }
        // 往右找
        if (!result) {
            result = hasSubTree(p1.right, p2)
        }
    }

    return result
}

/**
 * 以下是测试代码
 */

const tree1 = new Node(0, new Node(1, new Node(3)), new Node(2))

const tree2 = new Node(1, new Node(3))

console.log(hasSubTree(tree1, tree2))