Leetcode：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof《GitHub：https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_20_isSubStructure/Solution.java判断二叉树A是否包含子树B》题目描述：输入两棵二叉树A和B，判断B是否是A的子结构。（约定空树不是任何树的子结构）B是A的子结构，即A与B具有相同的结构和节点值。例如：给定treeA:3/\45/\12给定treeB:4/1返回true因为B和A的子树有相同的结构和节点值。例1：输入：A=[1,2,3],B=[3,1]输出：false示例2：输入：A=[3,4,5,1,2],B=[4,1]输出：true限制：0<=节点数<=10000解题思路：如果树B是树A的子结构，那么子结构的根节点可能是树A的任意一个节点。因此，判断树B是否是树A的子结构，需要完成以下两步：一阶遍历树A中的每个节点nA；(对应函数isSubStructure(A,B))判断树A是??否以nA为根节点的子树是否包含树B。(对应函数recur(A,B))算法流程：》名词规定：根节点树A的根节点称为节点A，树B的根节点称为节点B。recur(A,B)函数：1.终止条件：当节点B为空时：表示树B已经匹配（越过叶子节点），所以返回true；当节点A为空时：表示已经跨越了树A的叶子节点，即如果匹配失败，则返回false；当节点A和B的值不同时：表示匹配失败，返回false；2、返回值：判断A和B的左子节点是否相等，即recur(A.left,B.left)；判断A和B的右子节点是否相等，即recur(A.right,B.right);isSubStructure(A,B)函数：特例处理：当树A为空或树B为空时，直接返回false；返回值：如果树B是树A的子结构，则必须满足以下三个条件之一，所以用or|连接;以节点A为根节点的子树包含树B，对应recur(A,B)；B树是A树左子树的子结构，对应isSubStructure(A.left,B)；B树是A树右子树的子结构，对应isSubStructure(A.right,B)；设2。3。本质上就是对树A做一个前序遍历。复杂度分析：时间复杂度O(MN)：其中M和N分别为树A和树B的节点个数；树A的前序遍历占用0(M)，每次调用recur(A,B)占用O(N)。空间复杂度O(M)：当树A和树B都退化为链表时，递归调用的深度最大。当M≤N时，遍历树A和递归判断的总递归深度为M；当M>N时，最坏情况是遍历到树A的叶子节点，此时总递归深度为M。packagecom.nateshao.sword_offer.topic_20_isSubStructure;/***@dateCreatedby邵通杰on2021/11/2319:19*@微信公众号程序员千语*@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：判断二叉树A是否包含子树B*/classSolution{/***选答*@paramA*@paramB*@return*/publicstaticbooleanisSubStructure1(TreeNodeA,TreeNodeB){return(A!=null&&B!=null)&&(recur1(A,B)||isSubStructure1(A.left,B)||isSubStructure1(A.right,B));}publicstaticbooleanrecur1(TreeNodeA,TreeNodeB){if(B==null)returntrue;if(A==null||A.val!=B.val)returnfalse;returnrecur1(A.left,B.left)&&recur1(A.right,B.right);}/******************************************方法二***********************************************************************************************************************************************************************************************************************A的每个节点publicbooleanisSubStructure(TreeNodeA,TreeNodeB){if(A==null||B==null)returnfalse;//同意空树不是任何树的子结构returnrecur(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);}//同时遍历A和B的相同位置节点booleanrecur(TreeNodeA,TreeNodeB){//当B中某个结点为null时，不需要比较，直接返回true，比较其他结点if(B==null)returntrue;//如果相同位置的两个结点不相同，则返回false，不继续比较if(A==null||A.val!=B.val)returnfalse;//继续遍历比较returnrecur(A.left,B.left)&&recur(A.right,B.right);}publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}}参考链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p
