题目:Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
题目分析:判断二棵树是否相同,需要对树来进行遍历,然后判断每个节点的值是否相同,来判断树是否相同。
在这里,我先考虑的是先序遍历,也就是判断先访问根节点,然后在访问左子节点,右子节点。
python代码如下:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p == None and q == None:
return True
if p != None and q == None:
return False
if p == None and q != None:
return False
if p.val != q.val:
return False
if self.isSameTree(p.left, q.left) == False:
return False
if self.isSameTree(p.right, q.right) == False:
return False
return True
下面来看一下大佬的做法:
def isSameTree(self, p, q):
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p is q
在这个答案中,我们可以学到的是is语句的用法,对于一个变量而言,有3个属性,id,value,type,顾名思义,id就是变量的地址,value就是变量的值,而type就是变量的类型,如:
>>a = 1
>>b = 1
>>a is b
true
>>a = 1
>>b = 1.0
>>a is b
false
>>a == b
true
is要求二个变量完全相同,==的加强版,既要value相同,又要type相同,而value相同,表明了==的关系,所以成立的条件会相对而言比较宽松。
其实大佬的逻辑与我的逻辑是一致的,只是水平的差异,所以人家的语句很简练,而我很冗长,没关系,好好阅读大佬的程序就好。
对于这个问题,需要注意的是,对于None类型的节点而言,是没有.val的操作的。
其实最主要的是寻找相同的重复的模式,对于二个节点,无外乎四种情况,t1为None,t2为None,继续判断,t1为非None,t2为None,返回False退出即可,t1是None,t2为非None,返回False退出即可,t1是非None,t2为非None,需要比较二者的Val值,然后再依次判断左子节点的i情况,右子节点的情况。
从此题目得到的知识点:
第一,简化的书写,对于判断p, q是否是空节点的写法,直接写即可,可以不写==
即判断,p != None and q != None,写成p and q
p != None写成if p:同等类比的来写
第二,对于判断如果二者均为空则返回true,一个为空则返回false,采用is来实现