前言给定两棵二叉树A和B，如何判断B是否是A的子结构？本文将分享一个方案来解决这个问题。欢迎有兴趣的开发者阅读本文。思路分析在我的数据结构与算法实现系列文章——实现二叉搜索树中，我们知道一棵二叉树最多只能有两个子节点：左子节点和右子节点。那么，在这道题中，判断是否被包含，可以分两步实现：在树A中找到一个与树B的根节点值相同的节点R。如果树A的节点相同作为树B的根节点，再进行进一步的判断（比较两棵树的子结构），得到比较结果。如果结果为假，将递归树A的左子节点和右子节点与树B进行比较，直到任意一个树的叶子节点判断树A中以R为根节点的子树是否包含相同的子树结构为树B。如果树B为null，则表示树A包含树B。返回true。如果A树为null，则表示A树不包含B树，返回false如果比较的两个节点不相等，则表示A的当前子树不包含B树结构，返回false，否则继续递归，直到任意一棵树的叶子节点实现代码传递通过上一章的分析，我们得出了一个具体的思路。接下来将思路转化为代码，如下：实现main函数，判断B是否是A的子结构：递归树A和树B的节点进行比较，找到相同的节点再做进一步比较导出函数TreeSubstructure(treeA:BinaryTreeNode|null|undefined,treeB:BinaryTreeNode|null|undefined):boolean{letresult=false;if(treeA!=null&&treeB!=null){//两个节点相同if(treeA.key===treeB.key){//判断树A是??否包含树Bresult=treeAHaveTreeB(treeA,treeB);}//继续查找左子树和右子树if(!result){result=TreeSubstructure(treeA?.left,treeB);}if(!result){result=TreeSubstructure(treeA?.right,treeB);}}返回结果；}实现进一步的比较函数，判断树A的子节点是否包含与树B相同的结构functiontreeAHaveTreeB(treeA:BinaryTreeNode|空|未定义，treeB：BinaryTreeNode|空|undefined):boolean{//递归到树B的叶子节点，表示该节点存在于树A中if(treeB==null){returntrue;}//递归到树A的叶子节点表示该节点在树A中不存在if(treeA==null){returnfalse;}if(treeA.key!==treeB.key){returnfalse;}//左子树和右子树都是一样的以上代码，不明白的可以移步我的另一篇文章：递归的理解与实现，代码中也使用了自定义类型BinaryTreeNode。具体的类型定义请移步示例代码章节测试用例接下来我们用思路分析章节中提到的一个例子来测试上面的功能是否能正确执行。consttreeA:BinaryTreeNode={key:8,left:{key:8,left:{key:9},right:{key:2,left:{key:4},right:{key:7}}},右：{键：7}}；consttreeB:BinaryTreeNode={key:8,left:{key:9},right:{key:2}};constresult=TreeSubstructure(treeA,treeB);console.log("treeA包含treeB",result);示例代码本文使用的完整版代码请前往：TreeSubstructure.tsTreeSubstructure-test
