加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Python > 正文

Python3解leetcode Subtree of Another Tree

发布时间:2020-12-20 10:42:45 所属栏目:Python 来源:网络整理
导读:问题描述: Given two non-empty binary trees?s?and?t,check whether tree?t?has exactly the same structure and node values with a subtree of?s. A subtree of?s?is a tree consists of a node in?s?and all of this node‘s descendants. The tree?s?c

问题描述:

Given two non-empty binary trees?s?and?t,check whether tree?t?has exactly the same structure and node values with a subtree of?s. A subtree of?s?is a tree consists of a node in?s?and all of this node‘s descendants. The tree?s?could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    /    4   5
  /  1   2

Given tree t:

   4 
  /  1   2

Return?true,because t has the same structure and node values with a subtree of s.

?

Example 2:
Given tree s:

     3
    /    4   5
  /  1   2
    /
   0

Given tree t:

   4
  /  1   2

Return?false.

解题思路:

关于树的题目,第一反应就是利用DFS解答,此题也不例外。

代码:

 1 class Solution:
 2     def isSubtree(self,s: TreeNode,t: TreeNode) -> bool:
 3         def dfs(a,b):
 4             if not a or not b:  #若果a,b中存在null,处理手段
 5                 return not a and not b
 6             #以下处理时在a,b皆不为null的情况下进行讨论
 7             if a.val==b.val and dfs(a.left,b.left) and dfs(a.right,b.right):
 8                 return True
 9             if b is t:#当b时t的时候,判断a的左右子树分别与t是否相等
10                 return dfs(a.left,t) or dfs(a.right,t)
11             
12             return False
13         
14         return dfs(s,t)

第4、5行代码,将各种子树为空的情形缩略到一个条件判断中,精简了代码。

第7、8行代码,判断当前树是否和t树完全相同

第9、10行代码,只有当b是t的时候才生效,意思是如果该次执行是从第二个if递归过来的,那么就不进行判断,因为该次执行判断是当前树的子树与t的子树是否相同,并非是判断t是否与当前树相同。

最后12行代码,直接返回False即可。但如果返回的是dfs(a,t),代码执行时间会缩短75%,但是我没懂为何会缩短如此之多。

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读