LeetCode面试题04.10。CheckSubtree【Medium】【Python】【DFS】题目LeetcodeCheckSubtree。你有两棵非常大的二叉树：T1，有数万个节点；T2，有数万个节点。设计一个算法判断T2是否是T1的子树。如果T1有这样一个结点n，其子树与T2完全相同，那么T2就是T1的子树，也就是说，如果从结点n砍掉这棵树，得到的树与T2完全相同。示例1：输入：t1=[1,2,3],t2=[2]输出：true示例2：输入：t1=[1,null,2,4],t2=[3,2]输出：false提示：树中节点数的范围是[0,20000]。DFS的第一步是在t1中找到t2的起点。先判断t1的当前节点，如果不是则判断t1的左子树和t1的右子树。第二步：从找到的起点判断剩余点，t1和t2同步左右子树搜索。Python3代码#定义二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defcheckSubTree(self,t1:TreeNode,t2:TreeNode)->bool:ift1==None:returnFalseift2==None:returnTrue#在t1中找到t2的根returnself.dfs(t1,t2)orself.checkSubTree(t1.left,t2)orself.checkSubTree(t1.right,t2)defdfs(self,t1,t2):#t2结束ift2==None:returnTrue#t2没有结束，t1结束elift2!=Noneandt1==None:returnFalse#不等于elift2.val!=t1.val:returnFalse#等于，然后左右搜索else:returnself.dfs(t1.left,t2.left)andself.dfs(t1.right,t2.right)#注意这里是和代码地址GitHub链接相关题目LeetCode1367.LinkedListinBinaryTree二叉树中的列表
