572。另一棵树的子树题目来源：https://leetcode-cn.com/problems/subtree-of-another-tree清空二叉树s和t，检查s是否包含与t结构和节点值相同的子树.s的子树包括s的节点和该节点的所有后代。s也可以看作是它自己的子树。例1：给定树s:3/\45/\12给定树t:4/\12返回true，因为t作为s的子树具有相同的结构和节点值。示例2：给定树s:3/\45/\12/0给定树t:4/\12返回false。解题思路：深度优先搜索这里先分析一下题意：如果一棵二叉树是另一棵树的子树，它包含与另一棵树的子树相同的结构和节点值。根据例2可以看出，判断是否为子树，必须具有完全相同的结构和节点值。下面的s和t代表两棵二叉树。题目要求判断t是否是s的子树。现在将题意转化为实现代码编写的思路，判断两棵树是否相等。那么必须同时满足以下条件：当前两个树根节点的值相同；s的左子树与t的左子树相同；s的右子树与t的右子树相同。根据以上思路，本文考虑采用深度优化搜索的方法，枚举s的每个节点，判断该点的子树是否等于t。使用深度优先搜索检查，从根开始，同步遍历两棵树，判断对应的位置是否相等。具体代码实现如下。代码实现#定义一个二叉树节点。#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:defisSubtree(self,s:TreeNode,t:TreeNode)->bool:returnself.dfs(s,t)defdfs(self,c,t):#当c子树为空时，否则返回Falsec:returnFalsereturnself.is_same(c,t)orself.dfs(c.left,t)orself.dfs(c.right,t)defis_same(self,c,t):#两棵树Whenboth为空，也认为相同if(notc)and(nott):returnTrue#当其中一棵树为空，而另一棵树不为空时，此时不同if(notcand(nott)t)or(candnott):returnFalse#两棵树都不为空，如果值不同，它们也不同if(c.val!=t.val):returnFalse#当两者都不是满足以上条件，继续往下查看returnself.is_same(c.left,t.left)andself.is_same(c.right,t.right)实现上面的结果是使用depth-first搜索枚举s的每个节点来匹配t，然后解决《572. 另一个树的子树》问题的主要内容。欢迎关注微信公众号《书所集录》
