【Leetcode】100 : 相同的树(Python)
2021-03-30 15:28
标签：解法 语言 loading http 时间复杂度 基本 时间 结构 elf 题目： 给定两个二叉树，编写一个函数来检验它们是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 方法一： 这个题目很明显就可以用递归来做，有关树的题目用递归来做基本上是我们需要想到的首选！如果两个树是相同的，我们只需要比较其树根是相同的，同时递归调用比较树根的下一级子树是相同的，那么则可以得到整个树的结构是相同的，我自己的方法如下： 首先是设定递归的条件，然后在一级一级向下比较就可以了，思想和之前《剑指offer》当中的镜像二叉树的思想是相同的，后来发现自己第二步在进行递归的时候写多余了，没必要将树再往下推一步然后递归，可以直接进行递归，因此修改后如下： 这样两个if可以合并成一个if语句，减少了时间复杂度，同时也不需要再进行遍历到下一级之后再做递归，最后的成绩如下： 后来看了看其他人用java语言/go语言刷这道题的方法也基本这样，也就没必要再想迭代解法了。 【Leetcode】100 : 相同的树(Python) 标签：解法 语言 loading http 时间复杂度 基本 时间 结构 elf 原文地址：https://www.cnblogs.com/geeksongs/p/13579657.html题目解析：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p==q==None:
return True
if q==None or p==None:
return False
if p.val==q.val:
pleft=p.left
pright=p.right
qleft=q.left
qright=q.right
if self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right):
return True
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p==q==None:
return True
if q==None or p==None:
return False
if p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right):
return True
文章标题：【Leetcode】100 : 相同的树(Python)
文章链接：http://soscw.com/index.php/essay/70051.html