# 判断是否子树📕
# 题目描述
输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。
树的节点结构为:
/*
* 二叉树结点类
*/
class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
@前端进阶之旅: 代码已经复制到剪贴板
如下图, tree2为tree1的子结构
# 解题思路
假设需要判断的两颗树为tree1和tree2,需要判断tree2是否是tree1的子结构:
- 若
tree2是tree1的子结构,那么tree2的根节点必定为tree1中的某个节点, 所以要先找出这个节点; - 在
tree1中找到了这个节点后, 再判断这个节点下的所有子节点是否和tree2的子节点相同.
# coding
/*
* @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(
