前语
给定两颗二叉树A和B,如何判断B是不是A的子结构,本文将共享一个方案用来处理此问题,欢迎各位感兴趣的开发者阅览本文。
思路剖析
在我的数据结构与算法完成系列文章——完成二叉搜索树中,咱们知道了二叉树最多只能有两个子算法导论节点:左子节点、右子节点。那么,在本题中要判断是否包括,能够分为两步来完成:
-
在树A中找到和树B的根节点的值相同的节点R
- 假如树A的节点与树B的根结点相同,则前端是什么工作履行进一步的判断(比对两棵树的子结构)得出比对成果
- 假如得出的成果为false,别离递归树A的左子节点与右子节点跟树B进行比对,直至恣意一棵树的叶子节点
-
判断树A中以R为根节点的子树是否包括和树B相同的结构
- 假如树B为null则代表树A中包括树B,返回true
- 假如树A为null则代表树A中不包括树B,返回false
- 假如比对的两个节点不等,则代表当前A的子树中不包括树B结构,返回f算法设计与分析alse
- 不然,持续履行递归,前端开发直至恣意一棵树的叶子节点前端开发需要学什么
完成代码
经过上个章节的剖析,咱们现前端工程师已得出了详细的思路,接下来,咱们就将思路前端开发工程师转换为代码,如下所示:
- 完成主函数,判断B是否为A的子结构:
- 递归树A将其与树B的节点进行比对,找到相同的节点再做进一步的比对
export function TreeSubstructure(
treeA: BinaryTreeNode | null | undefined,
treeB: BinaryTreeNode | null | undefined
): boolean {
let result = false;
if (treeA != null && treeB != null) {
// 两个节点相同
if (treeA.key === treeB.key) {
// 判断树A中是否包括树B
result = treeAHaveTreeB(treeA, treeB);
}
// 持续寻觅左子树与右子树
if (!result) {
result = TreeSubstructure(treeA?.left, treeB);
}
if (!result) {
result = TreeSubstructure(treeA?.right, treeB);
}
}
return result;
}
- 完成进一步的比对算法是指什么函数,判断树A的子节点中是否包括跟树B相同的结构
function treeAHaveTreeB(
treeA: BinaryTreeNode | null | undefined,
treeB: BinaryTreeNode | null | undefined
): boolean {
// 递归到了树B的叶节点,代表该节点存在于树A中
if (treeB == null) {
return true;
}
// 递归到树A的叶节点,代表该节点不存在于树A中
if (treeA == null) {
return false;
}
if (treeA.key !== treeB.key) {
return false;
}
// 左子树与右子树都相同
return (
treeAHaveTreeB(treeA?.left, treeB?.left) &&
treeAHaveTreeB(treeA?.right, treeB?.right)
);
}
注意:上述代码中用到了递归,假如你对其不了解,能够移步我的另一篇文前端开发软件章:递归的了解与完成
代码中还用到了一个自界说类型BinaryTreeNode,详细的类型界说请移步示例代码章节。
测试用例
接下来,咱们用思路剖析章节中所举的例子来测试下上述函数能否正确履行。
const treeA: BinaryTreeNode = {
key: 8,
left: {
key: 8,
left: { key: 9 },
right: { key: 2, left: { key: 4 }, right: { key: 7 } }
},
right: { key: 7 }
};
const treeB: BinaryTreeNode = {
key: 8,
left: {
key: 9
},
right: {
key: 2
}
};
const result = TreeSubstructure(treeA, treeB);
console.log("treeA中包括treeB", result);
示例代码
本文所用代码完整版请移步:
- T测试抑郁症reeSubstructure.ts
- TreeSubstructure-test
写在最终
至此,文章就共享完毕了。
我是奇特的程序员,一位前端开发工程师。
假如你对我感兴趣,请移步我的个人网站,进一步了解。
- 文中如有过错,欢迎程序员客栈在谈论区纠正,假如这篇文算法工程师章帮到了你,欢迎点赞和重视
- 本算法的空间复杂度是指文首发于奇特的程序员公众号,未经许可禁止转载