Python3解leetcode Subtree of Another Tree

概述问题描述： 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 thi

问题描述：

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 False13         14         return dfs(s,t)

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

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

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

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

总结

以上是内存溢出为你收集整理的Python3解leetcode Subtree of Another Tree全部内容，希望文章能够帮你解决Python3解leetcode Subtree of Another Tree所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。