1. 题目描述

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

树的节点定义如下:

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

2. 思路分析

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

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

3. 代码实现

/**
 * 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));
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
57
58
59