题目描述

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值，返回 true

提示：

• 0 <= 节点个数 <= 10000

测试用例

用例1：

• 输入：A = [1,2,3], B = [3,1]
• 输出：false

用例2：

• 输入：A = [3,4,5,1,2], B = [4,1]
• 输出：true

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入二叉树数组A: ");
const a = readline().split(",").map(Number);

console.log("请输入二叉树数组B: ");
const b = readline().split(",").map(Number);

// 用队列
// var head = new TreeNode(arr[0]);
// var deque = [];
// deque.unshift(head);

// 把输入的数组转为二叉树数组存储
var arr1 = [];
var arr2 = [];

for (let i = 0; i < a.length; i++) {
  arr1[i] = new TreeNode(a[i]);
}

for (let i = 0; i < b.length; i++) {
  arr2[i] = new TreeNode(b[i]);
}

for (let i = 0; i <= arr1.length / 2 - 1; i++) {
  if (arr1[2 * i + 1]) {
    arr1[i].left = arr1[2 * i + 1];
  }
  if (arr1[2 * i + 2]) {
    arr1[i].right = arr1[2 * i + 2];
  }
}
for (let i = 0; i <= arr2.length / 2 - 1; i++) {
  if (arr2[2 * i + 1]) {
    arr2[i].left = arr2[2 * i + 1];
  }
  if (arr2[2 * i + 2]) {
    arr2[i].right = arr2[2 * i + 2];
  }
}

// 先序遍历输出

/* var preOrder = (root) => {
  if (root == null) {
    return;
  }
  console.log(root.val);
  preOrder(root.left);
  preOrder(root.right);
};

preOrder(arr1[0]);
preOrder(arr2[0]); 
*/

/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function (A, B) {
  // 有一个树为空了就返回false;
  if (A == null || B == null) {
    return false;
  }
  // 先序遍历A树
  // 判断A中有没有B，如果有B就直接返回true了
  return (
    judgeSubtree(A, B) ||
    isSubStructure(A.left, B) ||
    isSubStructure(A.right, B)
  );
};

// 判断树A中是否包含B
var judgeSubtree = function (A, B) {
  // 注意这里要先判断B，因为存在B和A同时遍历结束的情况，这种情况是要返回true的

  // B遍历完了还没有返回false，证明A中含有B，返回true
  if (B == null) {
    return true;
  }
  // A遍历结束了，还没有找到B，证明A不包含B，返回false
  if (A == null) {
    return false;
  }
  // 遇到不相等的val，证明A不包含B，返回false;
  if (A.val != B.val) {
    return false;
  }
  // 分别比较A和B的左子树，A和B的右子树，同时满足A包含B的条件，才返回true;
  return judgeSubtree(A.left, B.left) && judgeSubtree(A.right, B.right);
};

const res = isSubStructure(arr1[0], arr2[0]);
console.log("结果为: ", res);

/* 
  请输入二叉树数组A:
  1,2,3
  请输入二叉树数组B:
  3,1
  结果为:  false
*/

/* 
  请输入二叉树数组A:
  3,4,5,1,2
  请输入二叉树数组B:
  4,1
  结果为:  true
*/