判断是否子树

1. 题目描述

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

树的节点定义如下：

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

2. 思路分析

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

遍历树的函数hasSubTree：遍历 p1 的每个节点，如果当前节点的 value 和 p2 根节点的 value 相同，立即进入判断函数（下一个函数）；否则继续遍历
判断子树的函数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. 代码实现